有向无环图的拓扑排序

有向无环图（DAG），指不存在环的有向图。

点的入度，指以这个点为结束点的边数。

点的出度，指以这个点为出发点的边数。

拓扑序就是对于节点的一个排列使得若(u,v)∈E，那么u在排列中出现的位置一定在v前面。

而拓扑排序，则是一个用于求解拓扑序的方法（只需要求出一组解）

根据以上描述，我们可以发现我们只要每次找到入度为0的节点，把该节点输出，并删除该节点和这个节点所有的后继，就可以的到一个图的拓扑排序了。

像这张图，一种合法的拓扑排序就是1 2 4 3 5。

在这里使用队列来实现拓扑排序。

代码：

 1 #include<queue>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define N 42000
 5 using namespace std;
 6 queue<int>p;
 7 int next[N],num,to[N],head[N],n,m,a,b,r[N],u,pre[N],ans[N],sum;
 8 void add(int false_from,int false_to){
 9     next[++num]=head[false_from];
10     to[num]=false_to;
11     head[false_from]=num;
12 }
13 int main(){
14     scanf("%d%d",&n,&m);
15     for(int i=1;i<=m;++i){
16         scanf("%d%d",&a,&b);
17         add(a,b);
18         r[b]++;
19     }
20     for(int i=1;i<=n;++i)
21         if(!r[i])
22             p.push(i);
23     while(!p.empty()){
24         num=0;
25         u=p.front();
26         p.pop();
27         ans[++sum]=u;
28         for(int i=head[u];i;i=next[i]){
29             r[to[i]]--;
30             if(!r[to[i]])
31                 pre[++num]=to[i];
32         }
33         sort(pre+1,pre+num+1);
34         for(int i=1;i<=num;++i)
35             p.push(pre[i]);
36     }
37     for(int i=1;i<=sum;++i)
38         printf("%d ",ans[i]);
39     return 0;
40 }

View Code