您当前的位置: 首页 > 

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

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

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

拓扑图的有关知识:

  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             
关注
打赏
1662186765
查看更多评论
0.0359s