[学习笔记]拓扑排序

• 初始化一个int[] inDegree保存每一个结点的入度。
• 对于图中的每一个结点的子结点，将其子结点的入度加1。
• 选取入度为0的结点开始遍历，并将该节点加入输出。
• 对于遍历过的每个结点，更新其子结点的入度：将子结点的入度减1。
• 重复步骤3，直到遍历完所有的结点。
• 如果无法遍历完所有的结点，则意味着当前的图不是有向无环图。不存在拓扑排序。

 1 //topo sort;
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 #define N 10000+10
 5 
 6 int in[N];
 7 int n,m;
 8 
 9 queue<int>q;//需要字典序最小：priority_queue<int,vector<int>,greater<int> > q; /整数<int> q;
10 vector<int>edge[N];
11 void Topo()
12 {
13     for (int i=1;i<=n;i++) if (in[i]==0) q.push(i);
14     vector<int> ans;
15     while (!q.empty())
16     {
17         int q1=q.front(); q.pop();
18         ans.push_back(q1);
19         for (int i=0;i<edge[q1].size();i++)
20         {
21             int x=edge[q1][i];
22             in[x]--;
23             if (in[x]==0) q.push(x);    
24         }    
25     }
26     if (ans.size()==n)
27     {
28         for (int i=0;i<ans.size();i++)
29             printf("%d ",ans[i]);
30         printf("\n");
31         return ;
32     }
33     else printf("No Answer!");
34 }  
35 
36 int main()
37 {
38     memset(in,0,sizeof(0));
39     scanf("%d%d",&n,&m);
40     for (int i=1;i<=m;i++)
41     {
42         int x,y;
43         scanf("%d%d",&x,&y);
44         edge[x].push_back(y);
45         in[y]++; 
46     }
47     Topo();
48     return 0;
49 }

//topo sort;
#include <bits/stdc++.h>
using namespace std;
#define N 10000+10

int in[N];
int n,m;

queue<int>q;//需要字典序最小：priority_queue<int,vector<int>,greater<int> > q; /整数<int> q;
vector<int>edge[N];
void Topo()
{
    for (int i=1;i<=n;i++) if (in[i]==0) q.push(i);
    vector<int> ans;
    while (!q.empty())
    {
        int q1=q.front(); q.pop();
        ans.push_back(q1);
        for (int i=0;i<edge[q1].size();i++)
        {
            int x=edge[q1][i];
            in[x]--;
            if (in[x]==0) q.push(x);    
        }    
    }
    if (ans.size()==n)
    {
        for (int i=0;i<ans.size();i++)
            printf("%d ",ans[i]);
        printf("\n");
        return ;
    }
    else printf("No Answer!");
}  

int main()
{
    memset(in,0,sizeof(0));
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        edge[x].push_back(y);
        in[y]++;
    }
    Topo();
    return 0;
}

[学习笔记]拓扑排序

原文：https://www.cnblogs.com/Aqin-7/p/11380671.html