拓扑排序(Topological svorting)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

/**************************************************************** 
 * Description: topoSort
 * Author: Alex Li
 * Date: 2023-06-30 21:49:30
 * LastEditTime: 2024-01-29 23:15:02
****************************************************************/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n,m;
const int N=1000;
vector<int>  e[N],tp; //e[x]存点x的邻点，tp存拓扑序列;
int din[N];   //存结点的入度

bool TopoSort(){
     queue<int>  q;
     for (int i =1; i <=n; i++){
        if(din[i]==0) q.push(i);//将入度为0的结点入到q队列里。
        
     }
     while(q.size()){
        int x=q.front();  //把q队列首元素赋值给x
        q.pop();   //首元素出q队列
        tp.push_back(x);  //入到tp序列
    for (int i = 0; i < e[x].size(); i++){
        ////将刚出列x结点所有相联的结点的入度减1，如果入度是0，就入到q队列里
        if(--din[e[x][i]]==0)q.push(e[x][i]); 
          // for (auto y:e[x]) if(--din[y]==0)q.push(y);
        }
    }
     return tp.size()==n;  //如果拓扑序列个数和元素个数一样，说明可以拓扑排序 
     
}
int main(){
    int a,b;  //n是指结点数，m是边数
    cin>>n>>m;
    for (int  i = 0; i < m; i++){
        cin>>a>>b;
        e[a].push_back(b);  
        din[b]++;  //记录每个节点的入度
    }
    if(!TopoSort()) puts("TopoSort is not supported");
    else 
        for (int  i = 0; i <n; i++)cout<<tp[i];
return 0;        
}