首页 > 其他分享 >【笔记/模板】拓扑排序

【笔记/模板】拓扑排序

时间:2024-11-04 10:43:36浏览次数:1  
标签:int 拓扑 long 序列 顶点 排序 模板

www.luogu.com.cn

拓扑排序

定义与实现思路

拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足下面两个条件:

  1. 每个顶点出现且只出现一次。

  2. 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。

根据定义可知,我们可以使用队列+BFS的方式求出一个图的拓扑序列,方法如下:

  1. 存图的时候记录下每个点的前驱数(即入度)。

  2. 从图中选择一个 没有前驱(即入度为 \(0\))的顶点并输出,将其加入队列当中。

  3. 重复步骤 \(2\) 直到队列中的元素个数为 \(0\) 时,停止程序。

\(\bold tips\):通常,一个有向无环图可以有一个或多个拓扑排序序列。

代码实现

// Problem: B3644 【模板】拓扑排序 / 家谱树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/B3644
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e3 + 9;
const int INF = 0x3f3f3f3f;
vector<int> g[N];
int n, x, in[N];
queue<int> q;

int main()
{
	// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		while (cin >> x && x != 0)
		{
			g[i].push_back(x);
			in[x]++;
		}
	for (int i = 1; i <= n; i++)
		if (in[i] == 0)
		{
			cout << i << ' ';
			q.push(i);
		}
	while (!q.empty())
	{
		int x = q.front(); q.pop();
		for (auto i : g[x])
		{
			in[i]--;
			if (in[i] == 0) {
				cout << i << ' ';
				q.push(i);
			}
		}
	}
	return 0;
}

标签:int,拓扑,long,序列,顶点,排序,模板
From: https://www.cnblogs.com/ThySecret/p/18524703

相关文章

  • 【笔记/模板】树状数组
    原理解释树状数组是一种通过前缀和和差分的思想所进行的维护数组,从而以\(O(\logn)\)的时间复杂度进行修改和查询。一共有四种修改和查询的方式,分别是:单点修改\(+\)区间询问区间修改\(+\)单点询问单点修改\(+\)区间询问(二维)区间修改\(+\)区间询问其中利......
  • 【笔记/模板】树链剖分
    树链剖分树链剖分的基本思想通过将树分割成链的形式,从而把树形变为线性结构,减少处理难度。树链剖分(树剖/链剖)有多种形式,如重链剖分,长链剖分和用于Link/cutTree的剖分(有时被称作「实链剖分」),大多数情况下(没有特别说明时),「树链剖分」都指「重链剖分」。树链有如下几个特......
  • 【模板】矩阵运算
    不进行没必要的解释,主要记录模板。structMatrix{intn,m,rec[N][N]; //矩阵的长,宽和二维数组Matrix(int_n,int_m){n=_n,m=_m,memset(rec,0,sizeofrec);} //初始化函数voidreset(){n=0,m=0,memset(rec,0,sizeofrec);}......
  • 【笔记/模板】最近公共祖先(LCA)
    最近公共祖先(LCA)定义最近公共祖先(LowestCommonAncestor)简称LCA。对于一个树上的两个节点的最近公共祖先,是这两个点中的公共祖先里面离根最远的一个。性质可见OIWiki。向上标记法过程在两点中取得深度较大的一个点,让它不停的向上跳,同时标记所经过的每一个点,直到根节点,接......
  • 【笔记/模板】最小生成树
    www.luogu.com.cn概念/定义一个连通图的生成树是一个极小的连通子图,它包含图中全部的\(n\)个顶点,但只有构成一棵树的\(n-1\)条边。而最小生成树就是一个带权图的生成树,并且使得原图中边的权值最小的生成树,所谓最小是指边的权值之和小于或者等于其它生成树的边的权值之和。......
  • 【模板】Floyd算法
    Floyd算法原理Floyd算法用来求出任意两个节点之间的最短路。优点:代码少,思维简单,适用于除了负环以外的任何图。缺点:时间复杂度为\(O(n^3)\),空间复杂度为\(O(n^2)\)。而Floyd的核心原理是用动态规划实现的,定义一个二维数组\(f_{i,j}\),遍历图上的所有点\(k\),可以得......
  • 【模板】分块
    今天写分块的时候模板忘光了,故写以记之。CodeInitvoidinit(){sz=sqrt(n),block=n/sz+(n%sz!=0);for(inti=1;i<=block;i++)st[i]=(i-1)*sz+1,ed[i]=i*sz;ed[block]=n;for(inti=1;i<=block;i++)......
  • PbootCMS模板调用友情链接标签代码
    适用范围:全站任意地方标签作用:用于依次输出指定分组的友情链接调用代码:html {pboot:linkgid=*num=*}<ahref="[link:link]"title="[link:name]"><imgsrc="[link:logo]"></a>{/pboot:link}控制参数:gid=*:分组,必填num=*:数量,非必填,默认为10个可使用的列表......
  • PbootCMS模板调用幻灯片轮播图标签
    幻灯片轮播图列表:{pboot:slidenum=3gid=1}<ahref="[slide:link]"target="_blank"><imgsrc="[slide:src]"alt="[slide:title]"/></a>{/pboot:slide}控制参数:gid=*:分组,必填。num=*:数量,非必填,默认为5个。可用列表标......
  • pbootcms模板英文站搜索效果页面包屑显示优化
    打开 \apps\home\controller\SearchController.php 文件,根据版本替换代码:2.1.1版本:if(cookie('lg')=='cn'){//中文处理}else{//英文处理$content=str_replace('{pboot:pagetitle}',$this->config('search_title')?:......