您当前的位置: 首页 > 

判断是否为拓扑图、求拓扑序列模板

不牌不改 发布时间:2022-03-14 20:56:50 ,浏览量:4

拓扑图的有关知识:

  1. 广搜的应用
  2. 针对有向图来说,无向图没有拓扑序列
  3. 有向无环图一定存在拓扑序列(有向无环图也被称作拓扑图)
  4. 入度和出度
  5. 入度为0的点作为拓扑序的起点
  6. 一个图的拓扑序不一定唯一

过程:

将入度为0的点入队
while(队列不空) {
	取出队头t
	枚举队头t的所有出边(出边为t -> j)
		t的入度--(删除t -> j)
		判断t的入度是否为0,若为0则将t加入队列
}

代码

#include 
using namespace std;

const int N = 1e5+10;

int n, m, a, b;
int e[N> b,
		add (a, b),
		d[b] ++; // 统计每个点的入度
		
	if (topsort ()) {
		for (int i = 0;i             
关注
打赏
1688896170
查看更多评论
0.0477s