AcWing848有向图的拓扑排序

拓扑排序的流程：

1. 插入（a，b），表示a->b的关系，调用add(a,b),每次吧b的入度+1，d[b]++;
   然后调用topsort，返回1表示存在拓扑序列，返回0表示不存在拓扑序列。
2. 判断是否存在拓扑排序的逻辑：
   先把所有入度为0的点入队，这些都是可能的结果。
   取出队头t，然后出队
   因为是拉链法表示的有向图，因此访问t对应的所有出边j=e【i】
   然后删除t->j的关系，把j的入度-1，d[j] --,如果-1之后发现j的入度为0，那么j依然可能是新的拓扑序列的一员，需要把j入队！
3. 如果拓扑排序完了之后，把所有的点都曾入队过，那么存在拓扑序列。

#include<iostream>
#include<algorithm>
#include<cstring>
#define N 100086
using namespace std;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool topsort(){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];if(--d[j]==0){q[++tt]=j;}}}return tt==n-1;
}
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);d[b]++;}if(!topsort())puts("-1");else{for(int i=0;i<n;i++)cout<<q[i]<<' ';puts("");}return 0;
}