拓扑排序

学了AC自动机的拓扑排序优化，故来补一下。

拓扑排序是一种在DAG(有向无环图)上求解关于先后顺序的算法。其中它排序出来的结果叫做拓扑序。

拓扑排序其实可以抽象化成家谱：给定每个人的子辈，求所有人的辈分排序。

拓扑排序本质上就是一个 bfs。 首先遍历所有点，把入度为 $0$ 的点找出来，不难证明，这些点就是最高辈分的那些点，因为他们都没有父节点。把这些点入队，然后跑 bfs，将队头的点取出来，此时队头这个点，输出。此时做一个类似删点的操作，遍历这个点的所有邻居，因为这个点被删了，所以把它邻居的入度全部减 $1$。此时入度变成 $0$ 的点就入队，跑到结束为止。 删点只需处理入度。 注意点 1.不可以动这个图，删点只是名义上的，不是真的删，只需要处理入度就行了。 2.记得在输入时统计入度。 3.删完邻居边之后注意判入度和入队。

code

B3644 【模板】拓扑排序 / 家谱树

cpp
Copy
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>g[N];
queue<int>q;
int in[N];
int n,m;
int ans[N],cnt;
void topo(){
	for(int i=1;i<=n;i++){
		if(!in[i]){
			q.push(i);
		}
	}
	while(q.size()){
		int u=q.front();
		cout<<u<<" ";
		q.pop();
		for(int ne:g[u]){
			in[ne]--;
			if(!in[ne]){
				q.push(ne);
			}
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int t;
		while(cin>>t&&t){
			g[i].push_back(t);
			in[t]++;
		}
	}
	topo();
	return 0;
}