拓扑排序算法笔记

思想

拓扑，一看就是从图的开始开始开拓，并按被开拓到的顺序排序

拓扑排序的思想如下：

将入度为 \(0\) 的点删除，并记录它被删除的顺序，直到没有点则结束程序

代码也十分简单：

#include<bits/stdc++.h>
using namespace std;
bool b[100001];
int fat[100001];
vector<int>v[100001];
int main(){
	int n,m=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		fat[y]++;//记录入度
	}
	queue<int>q;
	for(int i=1;i<=n;i++){
		if(fat[i]==0){//将入度为0的点入队
			q.push(i);
			b[i]=1;
		}
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<v[u].size();i++){
			int nn=v[u][i];
			fat[nn]--;//入度减少
			if(fat[nn]==0){
				q.push(nn);//将入度为0的点入队
				b[nn]=1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(!b[i])cout<<i<<" ";	//也可以判断环上的点
	}
	return 0;
}

例题

P8655 [蓝桥杯 2017 国 B] 发现环

#include<bits/stdc++.h>
using namespace std;
bool b[100001];
int fat[100001];
vector<int>v[100001];
int main(){
	int n,m=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
		fat[x]++;
		fat[y]++;
	}
	queue<int>q;
	for(int i=1;i<=n;i++){
		if(fat[i]==1){
			q.push(i);
			b[i]=1;
		}
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<v[u].size();i++){
			int nn=v[u][i];
			fat[nn]--;
			if(fat[nn]==1){
				q.push(nn);
				b[nn]=1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(!b[i])cout<<i<<" ";	
	}
	return 0;
}

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