题意：给出元素个数与元素之间的关系，判断3种情况，能写出序列，有冲突，与不确定。
数据：
Sample Input
4 6 A<B A<C B<C C<D B<D A<B 3 2 A<B B<A 26 1 A<Z 0 0
Sample Output
Sorted sequence determined after 4 relations: ABCD. Inconsistency found after 2 relations. Sorted sequence cannot be determined.
第一次做读错题。。。。英语是硬伤啊~~~
总结拓扑排序算法过程。
一般使用邻接表保存图。记录每个度的入度与出度。其他问题就没什么了。
这题要注意的是需要先判断是否有环，在判断是否能成功。
**此题要注意的是一旦给出的序列能成功，后面的关系就直接忽略，直接输出成功。
总结Toposrot：
建立邻接表或邻接矩阵：
输入时，对出入度进行操作。
排序时：
找到入度为零的位置；
循环其出度次，将与其相连的位置入度减一；
该位置加入队中；
代码：
#include<iostream> #include<fstream> #include<cstring> using namespace std; char G[26][26]; int dm[26]; //每一列的和，即每个字母的入度 int dn[26]; //每一行的和，即每个字母的出度 int m,n; char result[27];
int TopoSort() { int index; //起点 int r = 0; int count; bool sorted = true; int dmt[26]; int dnt[26]; memcpy(dmt,dm,sizeof(dmt)); memcpy(dnt,dn,sizeof(dnt)); //找出入度为零的点 for(int j=0;j<n;j++) { count = 0; for(int i=0;i<n;i++) { if(0 == dmt[i]) { index = i; count++; } } if(0 == count) //发现环路 return count; if(count > 1) sorted = false; //从index开始，将与其相邻的入度减一； for(int i=0;i<dnt[index];i++) { dmt[G[index][i]-'A']--; } dmt[index] = -1; //index入度为-1 除去 result[r++] = index + 'A'; } result[r] = 0; if(sorted) return 1; //序**定 else return 2; //序列不确定 } int main() { int i,j,k; char str[4]; //freopen("input.txt","r+",stdin); cin>>n>>m; while(n&&m) { k = 0; int found = 0; //可以完全确定序列 int incons = 0; //发现冲突，即环路 memset(dm,0,sizeof(dm)); memset(dn,0,sizeof(dn)); memset(G,0,sizeof(G)); for(i=0;i<m;i++) { cin>>str; if(!found && !incons) { for(j=0;j<dn[str[0]-'A'];j++) //确定j为邻接表赋值 --指向出度 { if(G[str[0]-'A'][j] == str[2]) //当邻接表已有这个关系，则不操作 break; } if(j == dn[str[0]-'A']) { G[str[0]-'A'][j] = str[2]; //邻接表操作 dm[str[2]-'A'] ++; dn[str[0]-'A'] ++; } int res = TopoSort(); if(1 == res) //序列已确定 { found = i+1; } else if(0 == res) //发现冲突 { incons = i+1; } } } if(found) { cout<<"Sorted sequence determined after "<<found<<" relations: "<<result<<"."<<endl; } else if(incons) { cout<<"Inconsistency found after "<<incons<<" relations."<<endl; } else { cout<<"Sorted sequence cannot be determined."<<endl; } cin>>n>>m; }
return 0; }