有向无环图–又称为拓扑图 即有向图无环图 <==> 一个图有拓扑序
https://blog.csdn.net/login_sonata/article/details/78002042
入度 出度
算法:
1. 邻接表存储有向边,开一个数组d记录每个点入度,开一个结果数组res
2. 入度为0的点入队
3. 队列中的点依次弹出,记为t,记入res中
3. 拓展t的邻接点,入度减一,若入度为0,入队
4. 重复2,3直到队列为空
code
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 100005;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N];
int d[N];
vector<int> res;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void bfs()
{
int hh, tt;
hh = tt = 0;
for(int i = 1; i <= n; ++i)
//1 寻找入度为0的点
if(d[i] == 0)
q[tt ++] = i;
while(hh < tt){
int t = q[hh ++];
res.push_back(t);
for(int i = h[t]; i != -1; i = ne[i]){
int k = e[i];
//2 寻找入度为0的点
d[k] --;
if(d[k] == 0) q[tt ++] = k;
}
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
add(a, b);
//3 d数组 记录所有点的入度
d[b] ++;
}
bfs();
//4 如果有环,则环上所有点入度都不可能为0 所以如果 没有拓扑序列<==>有环<==>最后有入度不为0的点
for(int i = 1; i <= n; ++i)
if(d[i] != 0) {
cout << -1 << endl;
return 0;
}
for(int i = 0; i < n; ++i) cout << res[i] << " ";
}