拓扑排序算法笔记

ccr's notebook / 2023-08-17 / 原文

思想

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

拓扑排序的思想如下：

将入度为 \(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 【模板】拓扑排序 / 家谱树

其他

有时会有要字典序最小的情况，这是开个大根堆即可

点击查看代码

#include<bits/stdc++.h>
using namespace std;
bool b[100001];
int fat[100001],ans[100001];
vector<int>v[100001];
int main(){
	int T=0;int n,m=0;
	cin>>T;
	while(T--){
		for(int i=1;i<=n;i++){
			fat[i]=0;
			v[i].clear();
			b[i]=0;
		}
		cin>>n>>m;
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y;
			v[y].push_back(x);
			fat[x]++;
		}
		priority_queue<int>q;
		for(int i=1;i<=n;i++){
			if(fat[i]==0){
				q.push(i);
				b[i]=1;
			}
		}
		int tp=0;
		while(!q.empty()){
			int u=q.top();
			tp++;
			ans[tp]=u;
			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);
					b[nn]=1;
				}
			}
		}
		if(tp<n){
			cout<<"Impossible!"<<endl;
			continue;
		}
		for(int i=n;i>=1;i--){
			cout<<ans[i]<<" ";
		}
		cout<<endl;
	}
	return 0;
}