拓扑排序的原理 很早就知道了 但是 这个很简单的拓扑排序题 却写了好久、、、、对于各种标记不是很明朗。
拓扑排序的原理：
在一个图中（有向图），存在入度为0的点，把该点去掉，并删除该点所在的边，再找入度为0 的点，直到所有的顶点全被确定一个顺序。如果过程中入度为0的点大于一个，说明拓扑序列不唯一。
拓扑排序的应用：
一个有向图，一些的节点必须在另一些节点前面，适用于要求有某种顺序的题
代码附上：
#include <iostream> #include <stdio.h> using namespace std; bool map[27][27]; int flag;//flag=1矛盾 flag=2找到拓扑序列 int len,ll;//标记长度 int m,n; int in_degree[27];//入度 bool temp[27];//是否出现过该点 char result[27];//存储最终的顺序 bool num[27];//是否搜过该点 void topology(int x) { int i,j; int ind[27];ll=0; int res=0;//统计现有图中的顶点数 for (i=0;i<m;i++) { if (temp[i]) res++; ind[i]=in_degree[i]; num[i]=0; } int s=0; while(ll<res) { int tt=0;int v=0; for (j=0;j<m;j++)//找一个入度为0的点，确定该点并修改与其相连的点的入度 { if (num[j]==0&&temp[j]&&ind[j]==0)//没有搜过并且图中有该点，如果入度为0 { tt++; v=j; } } if(tt==0) {flag=1;break;}//没有入度为0的点 else if (tt>1) s=1; //有一个以上的入度为0的点，关系不能确定，但是依然要检查剩余的点中是否有矛盾 result[ll++]=v+'A'; num[v]=1; for (i=0;i<m;i++) { if(map[v][i]) ind[i]--; } } if (s==0&&flag==0&&ll==m) flag=2; len=x; } int main() { //freopen("Input.txt","r",stdin); while (cin>>m>>n&&(m+n)!=0) { flag=0;len=0; int i,j; for (i=0;i<=m;i++) { for(j=0;j<=m;j++) map[i][j]=0; in_degree[i]=0; temp[i]=0; } char a,b,c; for(i=0;i<n;i++) { cin>>a>>b>>c; map[a-'A'][c-'A']=1; in_degree[c-'A']++; temp[a-'A']=1;temp[c-'A']=1; if(flag==0) topology(i+1); } if (flag==1&&ll<m)//找到矛盾 { cout<<"Inconsistency found after "<<len<<" relations."<<endl; } else if (flag==2&&ll==m) { cout<<"Sorted sequence determined after "<<len<<" relations: "; for (i=0;i<ll;i++) { cout<<result[i]; } cout<<"."<<endl; } else { cout<<"Sorted sequence cannot be determined."<<endl; } } return 0; } 相关资源：微信小程序源码-合集3.rar