拓扑排序

拓扑排序的过程大概是这样的：
① 选择一个入度为0 的结点并直接输出。
② 删除这个结点以及与它关联的所有边。
③ 重复步骤①和②，直到找不到入度为0 的结点。

在一个有向图中，对所有的节点进行排序，要求没有一个节点指向它前面的节点。先统计所有节点的入度，对于入度为0的节点就可以分离出来，然后把这个节点指向的节点的入度减一。一直做改操作，直到所有的节点都被分离出来。如果最后不存在入度为0的节点，那就说明有环，不存在拓扑排序，也就是很多题目的无解的情况。

*1：删除1或2输出

*2：删除2或3以及对应边

*3：删除3或者4以及对应边

* 3：重复以上规则步骤

通过邻接矩阵来实现的代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 int ans[510][510];///邻接矩阵，记录二者是否有关联
 4 int n,indegree[510];///记录节点个数
 5 int queue[510];///保存拓扑
 6 void topsort()
 7 {
 8     int i,j,top,k=0;
 9     for(j=0; j<n; ++j)///遍历n次
10     {
11         for(i=1; i<=n; ++i)
12         {
13             if(indegree[i]==0)///找到入度为0的节点
14             {
15                 top=i;
16                 break;
17             }
18         }
19         queue[k++]=top;///当前第一名入队列，也可以直接输出
20         indegree[top]=-1;///该节点的入度更新为-1，避免重复入队列
21         for(i=1; i<=n; ++i)
22         {
23             if(ans[top][i])///删除与该店关联的边
24                 indegree[i]--;
25         }
26     }
27     for(i=0; i<k-1; ++i)
28         printf("%d ",queue[i]);
29     printf("%d
",queue[n-1]);
30 }
31 
32 int main()
33 {
34     int i,a,b,m;
35     while(scanf("%d%d",&n,&m)!=EOF)
36     {
37         memset(indegree,0,sizeof(indegree));///数组初始化为0
38         memset(ans,0,sizeof(ans));///数组初始化为0
39         for(i=0; i<m; ++i)
40         {
41             scanf("%d%d",&a,&b);
42             if(ans[a][b]==0)
43             {
44                 ans[a][b]=1;///二者有关联
45                 indegree[b]++;///记录前驱数量
46             }
47         }
48         topsort();
49     }
50     return 0;
51 }