首页 > 代码库 > poj1094Sorting It All Out 拓扑排序
poj1094Sorting It All Out 拓扑排序
做拓扑排序的题目，首先要知道两条定理：
1、最后得到的拓扑数组的元素个数如果小于n，则不存在拓扑序列。 （有圈）
2、如果一次入队的入度为零的点数大于1，则拓扑序列不唯一。 （关系不确定）
本题有一个默认的东西，如果到了第K（看K<m）步，能唯一确定一个序列，就不用管之后会不会产生矛盾。
这题的思路还是比较清晰的。输入也只有X<Y(只有<符号，并且X，Y都只是大写字母)，数据量比较小。不过边数没有限制，用链式前向星的话不太好，还是用邻接矩阵吧。每次用邻接矩阵要注意的是判断重边，做小生成树的时候是用初始化边为无穷大，然后每次取小的。但是这里没有边权，所以只要有边，赋值为1，就可以了。遇到重边的话，不能再加入度。
只需要拓扑排序就可以解决这个问题了。我就犯了画蛇添足的错误，我居然用floyd去判圈。这主要是对拓扑排序理解不够的原因。当出现的字母的数字小于n时，没出现的字母的入度是零，所以不影响拓扑排序产生的数据元素的个数。只有有圈的情况才会使得数组元素个数小于n。
还有，我犯了一个很二的错误。因为没输入一组数据就要做一次拓扑排序。我居然把统计入度的数组没有变化就用了。囧了。再声明一个数组，每次拓扑排序之前，把入度数组的数据复制过来就好了。
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N = 30;int ind[N],que[N], g[N][N],id[N];int iq,flag, T;void topo(int n){ int i,k,j=0,x; T=0; for(i=1;i<=n;i++) { id[i]=ind[i]; if(id[i]==0) que[j++]=i; } if(j>1) T=1; x=j; for(i=0;i<j;i++) { if(j-x>1) T=1; x=j; int u=que[i]; for(k=1;k<=n;k++) { if(g[u][k]&&u!=k) { id[k]--; if(id[k]==0) que[j++]=k; } } } iq=j;}void init(){ flag=0; memset(ind,0,sizeof(ind)); memset(g,0,sizeof(g));}int main(){ //freopen("test.txt","r",stdin); int n,m,i,j,k,t,a,b; char ch1,ch2,ch; while(scanf("%d%d",&n,&m)!=EOF) { if(!n) break; init(); t=0; for(k=1;k<=m;k++) { do scanf("%c",&ch1); while (!isalpha(ch1)) ; scanf("<%c",&ch2); if(flag) continue; a=ch1-64,b=ch2-64; if(a>n||b>n||a==b) flag=1; if(flag) {printf("Inconsistency found after %d relations.\n",k);continue;} if(g[a][b]) continue; g[a][b]=1; ind[b]++; topo(n); if(iq<n){flag=1;printf("Inconsistency found after %d relations.\n",k);continue;} if(iq==n&&!T){ flag=1; printf("Sorted sequence determined after %d relations: ",k); for(i=0;i<n;i++) printf("%c",que[i]+64); printf(".\n"); continue; } if(k==m&&!flag) printf("Sorted sequence cannot be determined.\n"); } } return 0;}
poj1094Sorting It All Out 拓扑排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。