搜索与图论-拓扑序列

为什么记录呢
因为不记录全忘了
虽然记了也不一定会看

1. 有向无环图一定有拓扑序列
2. 邮箱无环图 - 拓扑图

1. 入度为0的点作为起点
2. 入度为0的点入队列
3. 枚举出边 t->j
4. 删掉当前边，t->j . j的入度减1
5. 判断j的入度是否为0，来判断是否加入队列

1. 有环： 不存在入度为0的点

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>using namespace std;const int maxn = 100010;int h[maxn], e[maxn], ne[maxn], idx;int q[maxn],d[maxn];int n;int hh = 0, tt = -1;void add(int a, int b){e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}bool topsort(){while(hh <= tt){int t = q[hh++];for(int i = h[t]; i != -1; i = ne[i]){int j = e[i];d[j]--;if(d[j] == 0){q[++tt] = j;// cout<<"j: "<< j << " "; }}}// cout<<"tt " << tt << "n-1 "<< n-1 << '\n';return tt == n-1;}int main(){int m,a,b;memset(h , -1, sizeof h);cin >> n >> m;for(int i = 0; i < m; i++){cin>>a>>b;add(a,b);// cout<<"b  "<< b << " ";d[b]++;}for(int i = 1; i <= n; i++){if(d[i] == 0){// cout<<"i: " << i<<'\n';q[++tt] = i;}}if(topsort()){for(int i = 0; i < n; i++){cout<<q[i] << " ";}}else cout<<-1<< '\n';return 0;
}