搜索与图论——拓扑排序

有向图的拓扑排序就是图的宽度优先遍历的一个应用

有向无环图一定存在拓扑序列（有向无环图又被称为拓扑图），有向有环图一定不存在拓扑序列。无向图没有拓扑序列。

拓扑序列：将一个图排成拓扑序后，所有的边都是从前指向后的。

入度：有多少条边指向自己

出度：有多少条边指向别人

入度为0的点都可以排在最前边

#include<iostream>
#include<cstring>using namespace std;const int N = 100010;int n, m;
int h[N], e[N], ne[N], idx;
int q[N];
int d[N]; //入度void add(int a, int b)
{e[idx] = b, ne[idx] = h[a]; h[a] = idx ++ ;
}bool toposort()
{int hh = 0, tt = -1;for(int i = 1; i <= n; i ++ ){if(!d[i]) q[ ++ tt] = i; \\入度为零的点推入队列}while(hh <= tt){int t = q[hh ++ ];for(int i = h[t]; i != -1; i = ne[i]){int j = e[i]; //枚举t的所有出边jd[j] -- ; /删掉t -> j边，j的入度--if(d[j] == 0) q[ ++ tt] = j; //如果j的入度==0,推入队列}}return tt == n - 1; //如果队尾 == n - 1说明所有点都进过队列了,说明该图是一个有向无环图
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);while(m -- ){int a, b;cin >> a >> b;add(a, b);d[b] ++ ;}if(toposort()){for(int i = 0; i < n; i ++ ) cout << q[i] << " ";}else cout << -1 << endl;return 0;
}