拓扑排序

拓扑排序

先引入度数的概念：

度数=入度+出度

1. 入度：有多少条边指向自己。
2. 出度：有多少条边从自己指出。

啥是拓扑排序?

一个有向图，如果图中有入度为 0 的点，就把这个点删掉，同时也删掉这个点所连的边。

一直进行上面出处理，如果所有点都能被删掉，则这个图可以进行拓扑排序。

解题思路

1. 记录各个点的入度
2. 然后将入度为 0 的点放入队列
3. 将队列里的点依次出队列，然后找出所有出队列这个点发出的边，删除边，同事边的另一侧的点的入度 -1
4. 如果所有点都进过队列，则可以拓扑排序，输出所有顶点。否则输出-1，代表不可以进行拓扑排序。

代码部分：

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int e[N],ne[N],idx;//邻接表存储图
int h[N];
int q[N],hh,tt=-1;//队列保存入度为0的点，也就是能够输出的点，
int n,m;//保存图的点数和边数
int d[N];保存各个点的入度
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void topsort(){
    for(int i=1;i<=n;i++){//遍历一遍顶点的入度。
        if(d[i]==0)//如果入度为 0, 则可以入队列
            q[++tt]=i;
    }
    while(tt >= hh){//循环处理队列中点的
        int a = q[hh++];
        for(int i = h[a]; i != -1; i = ne[i]){//循环删除 a 发出的边
            int b = e[i];//a 有一条边指向b
            d[b]--;//删除边后，b的入度减1
            if(d[b] == 0)//如果b的入度减为 0,则 b 可以输出，入队列
                q[++tt] = b;
        }
    }
    if(tt == n - 1){//如果队列中的点的个数与图中点的个数相同，则可以进行拓扑排序
        for(int i = 0; i < n; i++){//队列中保存了所有入度为0的点，依次输出
            cout << q[i] << " ";
        }
    }
    else//如果队列中的点的个数与图中点的个数不相同，则可以进行拓扑排序
        cout << -1;//输出-1，代表错误
}
int main(){
    cin >> n >> m;//保存点的个数和边的个数
    memset(h,-1,sizeof h);//初始化邻接矩阵
    while(m--){//依次读入边
        int a,b;
        cin>>a>>b;
        d[b]++;//顶点b的入度+1
        add(a,b);//添加到邻接矩阵
    }
    topsort();//进行拓扑排序
}