拓扑排序总结

拓扑序：

定义：

给定n个点m条边的有向边，将n个点整理成一个序列，使得对于任意一条边i，总有i的出点在i的入店之前，这样的序列称之为图的拓扑序。

性质

1.只有有向无环图（DAG），才有拓扑序。
2.同一张图的拓扑序不一定唯一

拓扑排序：

整理拓扑序的算法称为拓扑排序。

拓扑排序的实现

1.统计每个点的入度in[i]
2.枚举所有点，并将入度为0的店插入队列（或者栈）
3.循环取出队头元素x输出，x指向的所有点y的入读-1，in[y]--；
4.当in[y]=0时，将y插入队列。 5.重复步骤3-4，直到队列为空。

code

CPP

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N=2e6+10;
int n,in[N];
vector<int> g[N];
queue<int> q;
void topo(){
	for(int i=1;i<=n;i++){
		if(in[i]==0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int x=q.front();
		cout<<x<<' ';
		q.pop();
		for(int i=0;i<g[x].size();i++){
			int y=g[x][i];
			in[y]--;
			if(in[y]==0) q.push(y);
		}
	}
	return ;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;){
    	int x; cin>>x;
    	if(x){
    		g[i].push_back(x);
			in[x]++;
		}
    	else i++;
	}
	topo();
    return 0;
}

常见题型

1.普通拓扑排序（板子）
例：B3644
2.找环
例：P2712
3.DP+拓扑
例：P1113

时间复杂度

O(N+M)

拓扑排序总结

文章操作

拓扑排序总结

拓扑序：

定义：

性质

拓扑排序：

拓扑排序的实现

code

常见题型

时间复杂度

相关推荐

评论

拓扑排序总结