拓扑排序入门

文章目录

  • 写在前面
  • 一些概念
  • 算法步骤
  • 字典序最大/最小的拓扑序列？
  • 模板
  • 例题
    • 3704. 排队
    • 家谱树
    • 奖金
    • P1983 [NOIP2013 普及组] 车站分级
    • 1639. 拓扑顺序

写在前面

昨晚cf div3的F就是一道基本上可以说板子的拓扑排序的题目，没有做出来感觉图论很早之前就看了，但是基本没有刷过什么题，开始补一下图论相关的知识点然后做点题目。

一些概念

拓扑序：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
上面是百度百科给出的拓扑序列的解释还是很全面、很能从本质上说明什么是拓扑序的
图中存在环 = = 图不是 D A G = = 图没有拓扑序 图中存在环==图不是DAG==图没有拓扑序 图中存在环==图不是DAG==图没有拓扑序
一个有向无环图可能存在多种拓扑排序的结果。

算法步骤

在拓扑排序的过程中，我们用一个数组或者任意容器记录到目前为止的拓扑序列，用一个队列或者任意容器记录所有不在当前拓扑序列中并且入度为0的顶点。

  1. 首先遍历整张图上的顶点,如果一个顶点入度为0，将它加入S
  2. 当S不为空时：
    • 在S中任取一个顶点x，将x加入到q的对位，并把x从S中删去
    • 遍历从x出发的边 x − > y x->y x−>y，把这条边删掉，如果y的入度变成了0，则将其加入到S中
  3. 循环结束时，如果所有点都加入了q，那么我们就找到了一个合法的拓扑序列，否则可以证明图中存在环
    1707918901744.png
    1707918986565.png

算法的时间复杂度： O ( n + m ) O(n+m) O(n+m)
解释：每个点最多入队一次出队一次，最坏情况是O(n)，对于删边操作，每条边最多被删一次
所以是 O ( n + m ) O(n+m) O(n+m)

字典序最大/最小的拓扑序列？

这字典序最大最小其实实现起来只需要将维护入度为0的点的容器换一下就可以了
我们可以选择优先队列或者set来维护入度为0的点，
就比如我们要求字典序最小的拓扑序列，我们用set去维护，每次从set中拿出的都是当前满足条件的编号最小的入度为0的点，也就是说满足了字典序最小。
最大的话可以重载一下，或者用优先队列（大根堆）来维护入度为0的点。

模板

	//ans用于存储拓扑排序的结果
	vector<int>ans;
	//队列保存当前入度为0的点
	queue<int>q;
	rep(i,1,n+m){
		if(!ind[i]){
			q.push(i);
			ans.pb(i);
		}
	}
	//bfs求拓扑序的过程，每次取出入度为0的点删除所有出边，如果删除出边导致产生新的入度为0的点
	//就将这个点加入ans和队列，用于扩展其他点
	while(q.size()){
		auto u=q.front();
		q.pop();
		for(auto v:g[u]){
			if(--ind[v.x]==0){
				q.push(v.x);
				ans.pb(v.x);
			}
		}
	}

例题

3704. 排队

3704. 排队

很裸的一道题目，对于x先于y，我们从x向y连一条边，然后跑一遍拓扑排序就是答案。

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;

void solve()
{
	int n,m;
	cin>>n>>m;
	vector<vector<int>>g(n+1);
	vector<int>ind(n+1);
	rep(i,1,m){
		int u,v;
		cin>>u>>v;
		g[u].pb(v);
		ind[v]++;
	}
	vector<int>ans;
	priority_queue<int,vector<int>,greater<int>>q;
	rep(i,1,n){
		if(!ind[i]){
			q.push(i);
		}
	}
	while(q.size()){
		auto u=q.top();
		q.pop();
		ans.pb(u);
		for(auto v:g[u]){
			if(--ind[v]==0){
				q.push(v);
			}
		}
	}
	for(auto it:ans){
		cout<<it<<' ';
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
	int _;
//	cin>>_;
//	while(_--)
	solve();
	return 0;
}

家谱树

AcWing 1191. 家谱树
基本上是拓扑排序的模板题。
和昨晚div3的F题目很像，所以来补拓扑排序了，多写几遍板子，熟悉起来。
这里提高课的时候视频里回答了一下如何求字典序最小的拓扑序
其实想一下不是很难，最简单的做法就是将普通队列换成优先队列，因为队列存储的是入度为零的点。

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;

void solve()
{
	int n;cin>>n;
	//vector存图
	vector<vector<int>>g(n+1);
	//ind统计每个点的入度
	vector<int>ind(n+1);
	rep(i,1,n){
		int v;
		while(cin>>v,v){
			g[i].pb(v);
			ind[v]++;
		}
	}
	//队列保存一下入度为0的点，并用于更新其他点
	queue<int>q;
	//记录拓扑序，如果是数组模拟队列就可以省去这一步
	vector<int>ans;
	//将所有入度为0的点入队
	rep(i,1,n){
		if(!ind[i]){
			q.push(i);
			ans.pb(i);
		}
	}
	//做一遍拓扑排序，也就是一遍bfs的过程
	while(q.size()){
		auto u=q.front();
		q.pop();
		for(auto v:g[u]){
			if(--ind[v]==0){
				q.push(v);
				ans.pb(v);
			}
		}
	}
	//输出拓扑序
	for(auto it:ans){
		cout<<it<<' ';
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
  	int _;
//	cin>>_;
//	while(_--)
	solve();
	return 0;
}

奖金

奖金

这道题目其实是和dp结合的一道题目。
每一条边 x → y x \rightarrow y x→y都是对于x的约束要求 x > y x>y x>y，所以出度为0的点也就是汇点是（除了最小值为100）没有其他约束的。
d [ u ] = m a x ( d [ u ] , d [ v ] + 1 ) , v 是所有 u 的所有邻点 d[u]=max(d[u],d[v]+1),v是所有u的所有邻点 d[u]=max(d[u],d[v]+1),v是所有u的所有邻点
我们只需要按拓扑序逆序从后往前递推一遍就能找到每个人奖金的最小值，然后每个点的d相加就是答案

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;
const int mod=1e9+7;


void solve()
{
	int n,m;
	cin>>n>>m;
	vector<vector<int>>g(n+1);
	vector<int>ans;
	vector<int>ind(n+1);
	rep(i,1,m){
		int u,v;
		cin>>u>>v;
		g[v].pb(u);
		ind[u]++;
	}
	queue<int>q;
	rep(i,1,n){
		if(!ind[i]){
			q.push(i);
			ans.pb(i);
		}
	}
	while(q.size()){
		auto u=q.front();
		q.pop();
		for(auto v:g[u]){
			if(--ind[v]==0){
				q.push(v);
				ans.pb(v);
			}
		}
	}
	if(ans.size()!=n){
		cout<<"Poor Xed"<<endl;
		return;
	}else{
		vector<int>d(n+1,100);
		for(auto u:ans){
			for(auto v:g[u]){
				if(d[u]+1>d[v]){
					d[v]=d[u]+1;
				}
			}
		}
		int res=0;
		rep(i,1,n){
			res+=d[i];
		}
		cout<<res<<endl;
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
  	int _;
//	cin>>_;
//	while(_--)
	solve();
	return 0;
}

P1983 [NOIP2013 普及组] 车站分级

P1983 [NOIP2013 普及组] 车站分级

这道题目有点和上面的奖金类似，和差分约束这些知识点密切相关。
分析一趟车次，对于这趟车中，所有停靠站的优先级必然高于没有停靠的，这样就会有一个关系
a 停 > = a 不停 + 1 a_停>=a_{不停}+1 a停​>=a不停​+1这个关系很像差分约束中的关系
对于一趟车次，就分为了停靠和不停靠这两类
以题目中给出的样例的第一趟车表示

ab8660c7ce272cfabc0092c20c33e32.jpg
边权为1。
然后按拓扑序跑一遍最长路，求的就是每个点的最长路的最大值。
这里由于连边很多而且是一个集合的所有点和另一个集合的所有点都连的有边，两边点的个数假设为 n 、 m n、m n、m那么，边数就是 n m nm nm很多
可以这样建边去优化，类似交换机的原理（hh学过计网的知识用上了），这样就把边数优化成了 m + n m+n m+n还是很巨大的一个优化的。
322983cef158fc304b3f5bd8f46c27d.jpg

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;

void solve()
{
	int n,m;
	cin>>n>>m;
	vector<vector<pii>>g(n+m+1);
	vector<int>ind(n+m+1);
	rep(i,1,m){
		vector<int>st(n+1,0);
		int start=n,ed=1,k;
		cin>>k;
		while(k--){
			int tmp;
			cin>>tmp;
			st[tmp]=1;
			start=min(start,tmp);
			ed=max(ed,tmp);
		}
		rep(j,start,ed){
			if(!st[j]){
				g[j].pb({i+n,0});
				ind[i+n]++;
			}else{
				g[i+n].pb({j,1});
				ind[j]++;
			}
		}
	}
	vector<int>ans;
	queue<int>q;
	rep(i,1,n+m){
		if(!ind[i]){
			q.push(i);
			ans.pb(i);
		}
	}
	while(q.size()){
		auto u=q.front();
		q.pop();
		for(auto v:g[u]){
			if(--ind[v.x]==0){
				q.push(v.x);
				ans.pb(v.x);
			}
		}
	}
	vector<int>d(n+m+1,0);
	rep(i,1,n)	d[i]=1;
	for(auto u:ans){
		for(auto v:g[u]){
			d[v.x]=max(d[v.x],d[u]+v.y);
		}
	}
	int res=0;
	rep(i,1,n){
		res=max(res,d[i]);
	}
	cout<<res<<endl;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
	int _;
//	cin>>_;
//	while(_--)
	solve();
	return 0;
}

1639. 拓扑顺序

1639. 拓扑顺序

暴力地去判断每个序列是否合法即可
对于每个序列我们判断在删完所有入边以后是否入度为0，如果为不0则说明拓扑序列不合法，反之则一直去删边，知道检查完最后一个点，均满足每个点在上一个点删完所有边之后入度为0，则说明是合法的拓扑序列。

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;

void solve()
{
	int n,m;
	cin>>n>>m;
	vector<vector<int>>g(n+1);
	vector<int>ind(n+1);
	rep(i,1,m){
		int u,v;
		cin>>u>>v;
		g[u].pb(v);
		ind[v]++;
	}
	int k;
	cin>>k;
	rep(i,0,k-1){
		vector<int>d(ind);
		vector<int>a(n+1);
		rep(j,1,n){
			cin>>a[j];
		}
		bool st=true;
		rep(j,1,n){
			if(d[a[j]]){
				st=false;
				break;
			}
			for(auto v:g[a[j]]){
				d[v]--;
			}
		}
		if(!st){
			cout<<i<<' ';
		}
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
	int _;
//	cin>>_;
//	while(_--)
	solve();
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/387365.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

ubuntu22.04@laptop OpenCV Get Started: 008_image_filtering_using_convolution

ubuntu22.04@laptop OpenCV Get Started: 008_image_filtering_using_convolution

ubuntu22.04laptop OpenCV Get Started: 008_image_filtering_using_convolution 1. 源由2. convolution应用Demo2.1 C应用Demo2.2 Python应用Demo 3. 重点分析3.1 identity矩阵3.2 all ones 5x5矩阵3.3 blur 5x5矩阵3.4 GaussianBlur 5x5矩阵3.5 medianBlur 5x5矩阵3.6 Sharpe…
阅读更多...
如何在极低成本硬件上落地人工智能算法 —— 分布式AI

如何在极低成本硬件上落地人工智能算法 —— 分布式AI

一、背景 分布式AI的发展前景非常广阔&#xff0c;随着5G、6G等高速网络通信技术的普及和边缘计算能力的提升&#xff0c;以及AI算法和硬件的不断优化进步&#xff0c;分布式AI将在多个领域展现出强大的应用潜力和市场价值&#xff1a; 1. **物联网&#xff08;IoT&#xff0…
阅读更多...
JVM（1）基础篇

JVM（1）基础篇

1 初始JVM 1.1 什么是JVM JVM 全称是 Java Virtual Machine&#xff0c;中文译名 Java虚拟机。JVM 本质上是一个运行在计算机上的程序&#xff0c;他的职责是运行Java字节码文件。 Java源代码执行流程如下&#xff1a; 分为三个步骤&#xff1a; 编写Java源代码文件。 使用…
阅读更多...
Swift Combine 使用 flatMap 和 catch错误处理 从入门到精通十三

Swift Combine 使用 flatMap 和 catch错误处理 从入门到精通十三

Combine 系列 Swift Combine 从入门到精通一Swift Combine 发布者订阅者操作者 从入门到精通二Swift Combine 管道 从入门到精通三Swift Combine 发布者publisher的生命周期 从入门到精通四Swift Combine 操作符operations和Subjects发布者的生命周期 从入门到精通五Swift Com…
阅读更多...
什么是 Flet？

什么是 Flet？

什么是 Flet&#xff1f; Flet 是一个框架&#xff0c;允许使用您喜欢的语言构建交互式多用户 Web、桌面和移动应用程序&#xff0c;而无需前端开发经验。 您可以使用基于 Google 的 Flutter 的 Flet 控件为程序构建 UI。Flet 不只是“包装”Flutter 小部件&#xff0c;而是…
阅读更多...
为什么说技术进步很慢？ —— 技术的先进性与其当下价值的不匹配

为什么说技术进步很慢？ —— 技术的先进性与其当下价值的不匹配

一、背景 技术进步是否缓慢是一个相对的概念&#xff0c;需要在不同的领域和时间段内进行分析。以下是一些不同领域中可能造成技术进步看似缓慢的原因&#xff1a; 1. **基础研究瓶颈**&#xff1a;许多先进技术的发展依赖于基础科学的突破&#xff0c;而这些突破往往需要长时…
阅读更多...
MySQL-----函数篇

MySQL-----函数篇

目录 ▶ 字符串函数 ▶ 数值函数 ▶ 日期函数 ▶ 流程函数 ▶ 简介 函数是指一段可以直接被另一段程序调用的程序或代码。 ▶ 字符串函数 函数描述实例ASCII(s)返回字符串 s 的第一个字符的 ASCII 码。 返回 CustomerName 字段第一个字母的 ASCII 码&#xff1a; S…
阅读更多...
vuex中Actions详解，代码示例

vuex中Actions详解，代码示例

Vuex 中的 Actions 是用于触发mutations 的一种方式&#xff0c;它可以包含异步操作&#xff0c;并通过提交(commit)mutations 来改变 store 的状态。以下是 Actions 的详细介绍、使用步骤和示例代码&#xff1a; Actions 的介绍&#xff1a; Actions 是 Vuex 中的一个重要概…
阅读更多...
第一篇【传奇开心果系列】Python的pyttsx3库技术点案例示例：文本转换语言

第一篇【传奇开心果系列】Python的pyttsx3库技术点案例示例：文本转换语言

传奇开心果短博文系列 系列短博文目录Python的pyttsx3库技术点案例示例系列 短博文目录前言一、pyttsx3主要特点和功能介绍二、pyttsx3文字转语音操作步骤介绍三、多平台支持介绍和示例代码四、多语言支持介绍和示例代码五、自定义语言引擎介绍和示例代码六、调整语速和音量介绍…
阅读更多...
JavaWeb学习|i18n

JavaWeb学习|i18n

学习材料声明 所有知识点都来自互联网&#xff0c;进行总结和梳理&#xff0c;侵权必删。 引用来源&#xff1a;尚硅谷最新版JavaWeb全套教程,java web零基础入门完整版 i18n 国际化&#xff08;Internationalization&#xff09;指的是同一个网站可以支持多种不同的语言&…
阅读更多...
文心一言4.0 VS ChatGPT4.0哪家强？！每月60块的文心一言4.0值得开吗？

文心一言4.0 VS ChatGPT4.0哪家强？！每月60块的文心一言4.0值得开吗？

大家好&#xff0c;我是木易&#xff0c;一个持续关注AI领域的互联网技术产品经理&#xff0c;国内Top2本科&#xff0c;美国Top10 CS研究生&#xff0c;MBA。我坚信AI是普通人变强的“外挂”&#xff0c;所以创建了“AI信息Gap”这个公众号&#xff0c;专注于分享AI全维度知识…
阅读更多...
C++ Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统（3） 保存表格数据

C++ Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统（3） 保存表格数据

对上两篇篇的工作C Qt框架开发| 基于Qt框架开发实时成绩显示排序系统&#xff08;1&#xff09;-CSDN博客和C Qt框架开发 | 基于Qt框架开发实时成绩显示排序系统&#xff08;2&#xff09;折线图显示-CSDN博客继续优化&#xff0c;增加一个保存按钮&#xff0c;用于保存成绩数据…
阅读更多...
【Java记】数据类型与变量

【Java记】数据类型与变量

一、数据类型 在Java中数据类型主要分为两类&#xff1a;基本数据类型和引用数据类型。基本数据类型有四类八种&#xff1a; 四类&#xff1a;整型、浮点型、字符型以及布尔型八种&#xff1a; 数据类型 关键字 内存占用 范围 字节型 byte 1 字节 -128~ 127 短整型 …
阅读更多...
基于GPT-4一键完成数据分析全流程的AI Agent: Streamline Analyst

基于GPT-4一键完成数据分析全流程的AI Agent: Streamline Analyst

大型语言模型&#xff08;LLM&#xff09;的兴起不仅为获取知识和解决问题开辟了新的可能性&#xff0c;而且催生了一些新型智能系统&#xff0c;例如旨在辅助用户完成特定任务的AI Copilot以及旨在自动化和自主执行复杂任务的AI Agent&#xff0c;使得编程、创作等任务变得高效…
阅读更多...
AndroidStdio修改安卓模拟器的安装位置

AndroidStdio修改安卓模拟器的安装位置

AndroidStdio修改安卓模拟器的安装位置 1.删除原有的虚拟机 可以直接删除这个avd文件&#xff0c;放心大胆删除 在这个目录下可以看到.avd文件和.ini文件。.avd占了我10G.上图是我转移.avd后截的。发现这个.ini文件&#xff0c;.ini文件就是配置文件&#xff0c;就像mysql安装…
阅读更多...
ElasticSearch快速开始

ElasticSearch快速开始

目录 全文检索 全文检索的原理 什么是倒排索引 ElasticSearch介绍 ElasticSearch应用场景 ElasticSearch下载安装&#xff08;windows&#xff09; 客户端Kibana安装 Elasticsearch安装分词插件 ElasticSearch快速开始 ElasticSearch索引操作 创建索引 查询索引 删…
阅读更多...
蓝桥杯电子类单片机提升二——串口发送与接收

蓝桥杯电子类单片机提升二——串口发送与接收

目录 单片机资源数据包_2023 一、串口收发数据的介绍 1.波特率&#xff08;Baud Rate&#xff09; 2.帧格式 3.SBUF寄存器&#xff08;Serial Buffer&#xff09; 4.中断处理 二、如何从stc-isp获取串口收发数据的代码 1.代码的获取 2.代码的修改 1&#xff09;第一步…
阅读更多...
HarmonyOS鸿蒙学习基础篇 - 自定义组件（一）

HarmonyOS鸿蒙学习基础篇 - 自定义组件（一）

前言 在ArkUI中&#xff0c;UI显示的内容均为组件&#xff0c;由框架直接提供的称为系统组件&#xff0c;由开发者定义的称为自定义组件。在进行 UI 界面开发时&#xff0c;通常不是简单的将系统组件进行组合使用&#xff0c;而是需要考虑代码可复用性、业务逻辑与UI分离&#…
阅读更多...
SpringIOC之support模块ResourceBundleMessageSource

SpringIOC之support模块ResourceBundleMessageSource

博主介绍&#xff1a;✌全网粉丝5W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战&#xff0c;博主也曾写过优秀论文&#xff0c;查重率极低&#xff0c;在这方面有丰富的经验…
阅读更多...
Java微服务学习Day1

Java微服务学习Day1

文章目录 认识微服务服务拆分及远程调用服务拆分服务远程调用提供者与消费者 Eureka注册中心介绍构建EurekaServer注册user-serviceorder-service完成服务拉取 Ribbon负载均衡介绍原理策略饥饿加载 Nacos注册中心介绍配置分级存储负载均衡环境隔离nacos注册中心原理 认识微服务…
阅读更多...
最新文章

Copyright @ 2022~2023