程序员经验分享-hwhale

[洛谷] [NOIP2018 提高组] 旅行 加强版 - 基环树

2023-11-12

题目链接：https://www.luogu.com.cn/problem/P5049

题目描述

小 Y 是一个爱好旅行的 OIer。她来到 X 国，打算将各个城市都玩一遍。

小Y了解到， X国的 n 个城市之间有 m 条双向道路。每条双向道路连接两个城市。 不存在两条连接同一对城市的道路，也不存在一条连接一个城市和它本身的道路。并且， 从任意一个城市出发，通过这些道路都可以到达任意一个其他城市。小 Y 只能通过这些 道路从一个城市前往另一个城市。

小 Y 的旅行方案是这样的：任意选定一个城市作为起点，然后从起点开始，每次可 以选择一条与当前城市相连的道路，走向一个没有去过的城市，或者沿着第一次访问该 城市时经过的道路后退到上一个城市。当小 Y 回到起点时，她可以选择结束这次旅行或 继续旅行。需要注意的是，小 Y 要求在旅行方案中，每个城市都被访问到。

为了让自己的旅行更有意义，小 Y 决定在每到达一个新的城市（包括起点）时，将 它的编号记录下来。她知道这样会形成一个长度为 nn 的序列。她希望这个序列的字典序 最小，你能帮帮她吗？ 对于两个长度均为 nn 的序列 AA 和 BB，当且仅当存在一个正整数 xx，满足以下条件时， 我们说序列 AA 的字典序小于 BB。

对于任意正整数 1 ≤ i < x1≤i<x，序列 A 的第 i 个元素Ai 和序列 B 的第 i 个元素 Bi相同。
序列 A 的第 x 个元素的值小于序列 B 的第 x 个元素的值。

输入格式

输文件共 m+1 行。第一行包含两个整数 n,m(m≤n)，中间用一个空格分隔。

接下来 m 行，每行包含两个整数 u,v(1≤u,v≤n) ，表示编号为 u 和 v 的城市之 间有一条道路，两个整数之间用一个空格分隔。

输出格式

输出文件包含一行，nn 个整数，表示字典序最小的序列。相邻两个整数之间用一个 空格分隔。

输入

6 5 
1 3 
2 3 
2 5 
3 4 
4 6

输出

1 3 2 5 4 6

输入

6 6 
1 3 
2 3 
2 5 
3 4 
4 5 
4 6

输出：

1 3 2 4 5 6

该题m有两种情况，对于m = n - 1的情况，这是一颗树，我们只需要从1开始，往后遍历时，每次选择所连的点（未被访问过）中，编号最小的那个（贪心）
对于m = n的情况下，图中绝对会有一个环，这种图叫做基环树，
遇见基环树，首要的任务是找环 ：
① 在学习Tarjan算法的时候，我们可以知道改环中任意两点都是可以相互到达的（SCC），所以说我们可以用Tarjan算法来找出环 最稳妥
② 可以用dfs来模拟Tarjan算法的过程来找环
以下为本人两种常用的dfs找环的代码，均可通过此题

bool vis[500007];
int in[500007],tot,rt;
int getLoop(int u,int fa) {
	if(vis[u]) {
		rt = u;
		return 1;
	}
	int tmp;
	vis[u] = true;
	for(int i=head[u]; ~i; i=e[i].nex) {
		int to = e[i].v;
		if(to == fa) continue;
		tmp = getLoop(to,u);
		if(tmp) {
			if(tmp == 1) {
				in[u] = 1;
				if(u != rt) return 1;
			}
			return 2;
		}
	}
	return 0;
}

int getLoop2(int u,int fa) {
	vis[u] = true;
	for(int i=head[u]; ~i; i=e[i].nex) {
		int to = e[i].v;
		if(to == fa) continue;
		if(vis[to]) {
			in[u] = 1;
			return to;
		} else {
			int ret = getLoop2(to,u);
			if(ret == 0) return 0;
			if(ret == -1) continue;
			in[u] = 1;
			if(ret == u) return 0;
			else return ret;
		}
	}
	return -1;
}

对于基环树的情况，大致有两种复杂度的情况{
1. 找到环，然后枚举环上的边，断掉一条边之后，便到了树的情况
2. 因为基环树比树多了一条边，所以在 dfs找答案的时候就可以选择一条边不走。按照贪心策略在dfs过程中，考虑在什么情况下会选择舍弃一条边？{
① 毋庸置疑，首先我们舍弃的这一条边是在环上的
② 舍弃了这条边之后，就立即进行回溯，因为舍弃的边连接的是当前点的最大儿子节点
③ 我们在回溯之后，再往后走的那个点的编号一定是比舍弃的那条边连接的点要小
}
}

以上两种找环的方式时间复杂度相差不大（几乎没有差距）
在这里插入图片描述

int cnt,head[500007],n,m,flag;
vector<int> ans;
struct node {
	int v,nex,u;
} e[maxn];
void add(int u,int v) {
	e[cnt].u = u;
	e[cnt].v = v;
	e[cnt].nex = head[u];
	head[u] = cnt ++;
}
void init() {
	cnt = 0;
	for(int i=0; i <= 500000; i++) head[i] = -1;
}
bool vis[500007];
int in[500007],tot,rt;
int getLoop(int u,int fa) {
	if(vis[u]) {
		rt = u;
		return 1;
	}
	int tmp;
	vis[u] = true;
	for(int i=head[u]; ~i; i=e[i].nex) {
		int to = e[i].v;
		if(to == fa) continue;
		tmp = getLoop(to,u);
		if(tmp) {
			if(tmp == 1) {
				in[u] = 1;
				if(u != rt) return 1;
			}
			return 2;
		}
	}
	return 0;
}
int getLoop2(int u,int fa) {/// pre_version
	vis[u] = true;
	for(int i=head[u]; ~i; i=e[i].nex) {
		int to = e[i].v;
		if(to == fa) continue;
		if(vis[to]) {
			in[u] = 1;
			return to;
		} else {
			int ret = getLoop2(to,u);
			if(ret == 0) return 0;
			if(ret == -1) continue;
			in[u] = 1;
			if(ret == u) return 0;
			else return ret;
		}
	}
	return -1;
}
void dfs(int u,int fa) {
	ans.push_back(u);
	vis[u] = true;
	vector<int> vet;
	for(int i=head[u]; ~i; i=e[i].nex) {
		int to = e[i].v;
		if(vis[to]) continue;
		vet.push_back(to);
	}
	sort(vet.begin(),vet.end());
	int siz = vet.size();
	for(int i=0; i<siz; i++) {
		int to = vet[i];
		if(vis[to]) continue;
		if(flag && i == siz - 1 && in[u] && in[to] && to > fa) {
			flag = 0;
			continue;
		}
		if(i + 1 < siz) dfs(to,vet[i+1]);
		else dfs(to,fa);
	}
}
int main() {
	n = read,m = read;
	init();
	for(int i=1; i<=m; i++) {
		int u = read,v = read;
		add(u,v),add(v,u);
	}
	memset(vis,0,sizeof vis);
	if(n == m) getLoop(1,0),flag = 1;/// ac 2 3 4 5
	memset(vis,0,sizeof vis);
	dfs(1,n+1);
	for(int i=1; i<=n; i++) {
		printf("%d%c",ans[i-1],i<n?' ':'\n');
	}
	return 0;
}
/**
6 6
1 3
2 3
2 5
3 4
4 5
4 6

**/

Tarjan做法：
在这里插入图片描述
时间相差不大，可能多了个 stl 的常数吧

int cnt,head[500007],n,m,flag;
vector<int> ans;
struct node {
	int v,nex,u;
} e[maxn];
void add(int u,int v) {
	e[cnt].u = u;
	e[cnt].v = v;
	e[cnt].nex = head[u];
	head[u] = cnt ++;
}
void init() {
	cnt = 0;
	for(int i=0; i <= 500000; i++) head[i] = -1;
}
bool vis[500007];
int in[500007],tot,tim;
int dfn[500007],low[500007];///,pos[500007];
stack<int> st;///Tarjan use
void Tarjan(int x,int fa) {
	dfn[x] = low[x] = ++ tim;
	st.push(x);
	vis[x] = 1;
	for(int i=head[x]; ~i; i=e[i].nex) {
		int to = e[i].v;
		if(to == fa) continue;
		if(!dfn[to]) {
			Tarjan(to,x);
			low[x] = min(low[x],low[to]);
		} else if(vis[to] == 1) {
			low[x] = min(low[x],dfn[to]);
		}
	}
	if(low[x] == dfn[x]) {
		vector<int> path;
		path.push_back(x);
		while(st.top() != x) {
			path.push_back(st.top());
			vis[st.top()] = 0;
			st.pop();
		}
		st.pop();
		if(path.size() >= 2) {
			for(int i=0; i<path.size(); i++) in[path[i]] = 1;
			return ;
		}
	}
}
void dfs(int u,int fa) {
	ans.push_back(u);
	vis[u] = true;
	vector<int> vet;
	for(int i=head[u]; ~i; i=e[i].nex) {
		int to = e[i].v;
		if(vis[to]) continue;
		vet.push_back(to);
	}
	sort(vet.begin(),vet.end());
	int siz = vet.size();
	for(int i=0; i<siz; i++) {
		int to = vet[i];
		if(vis[to]) continue;
		if(flag && i == siz - 1 && in[u] && in[to] && to > fa) {
			flag = 0;
			continue;
		}
		if(i + 1 < siz) dfs(to,vet[i+1]);
		else dfs(to,fa);
	}
}
int main() {
	n = read,m = read;
	init();
	for(int i=1; i<=m; i++) {
		int u = read,v = read;
		add(u,v),add(v,u);
	}
	memset(vis,0,sizeof vis);
	if(n == m) Tarjan(1,0),flag = 1;/// ac 2 3 4 5
	memset(vis,0,sizeof vis);
	dfs(1,n+1);
	for(int i=1; i<=n; i++) {
		printf("%d%c",ans[i-1],i<n?' ':'\n');
	}
	return 0;
}
/**
6 6
1 3
2 3
2 5
3 4
4 5
4 6

**/

本题在找环的过程中，像极了2017年蓝桥杯决赛的一道题 发现环
其实这个题再想一下的话，就可以发现，可以用拓扑排序做出来
方法大同小异咯
干脆也写了一下，拓扑排序写法：
在这里插入图片描述

#define Clear(x,val) memset(x,val,sizeof x)
int cnt,head[500007],n,m,flag;
vector<int> ans;
struct node {
	int v,nex,u;
} e[maxn];
void add(int u,int v) {
	e[cnt].u = u;
	e[cnt].v = v;
	e[cnt].nex = head[u];
	head[u] = cnt ++;
}
void init() {
	cnt = 0;
	for(int i=0; i <= 500000; i++) head[i] = -1;
}
bool vis[500007];
int in[500007],tot,tim;
int dfn[500007],low[500007];///,pos[500007];
stack<int> st;///Tarjan use
int deg[500007];
void topoSort() {
	queue<int> que;
	for(int i=1; i<=n; i++) {
		if(deg[i] == 1) que.push(i),vis[i] = 1;
	}
	while(que.size()) {
		int frt = que.front();
		que.pop(); 
		if(deg[frt] == 1) in[frt] = 0;
		for(int i=head[frt]; ~i; i=e[i].nex) {
			int to = e[i].v;
			deg[to] --;
			if(deg[to] == 1) que.push(to);
		}
	}
}
void dfs(int u,int fa) {
	ans.push_back(u);
	vis[u] = true;
	vector<int> vet;
	for(int i=head[u]; ~i; i=e[i].nex) {
		int to = e[i].v;
		if(vis[to]) continue;
		vet.push_back(to);
	}
	sort(vet.begin(),vet.end());
	int siz = vet.size();
	for(int i=0; i<siz; i++) {
		int to = vet[i];
		if(vis[to]) continue;
		if(flag && i == siz - 1 && in[u] && in[to] && to > fa) {
			flag = 0;
			continue;
		}
		if(i + 1 < siz) dfs(to,vet[i+1]);
		else dfs(to,fa);
	}
}
int main() {
	n = read,m = read;
	init();
	for(int i=1; i<=m; i++) {
		int u = read,v = read;
		add(u,v),add(v,u);
		deg[u] ++;
		deg[v] ++;
	}
	memset(vis,0,sizeof vis);
	if(n == m) Clear(in,1),topoSort(),flag = 1;
	memset(vis,0,sizeof vis);
	dfs(1,n+1);
	for(int i=1; i<=n; i++) {
		printf("%d%c",ans[i-1],i<n?' ':'\n');
	}
	return 0;
}

参考博客：https://blog.csdn.net/xyyxyyx/article/details/103010642

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

图论

算法

概率论

[洛谷] [NOIP2018 提高组] 旅行 加强版 - 基环树 的相关文章

  • vs中报错error C4996: 'wcstombs': This function or variable may be unsafe

    遇到这样的情况就是缺少宏 所以需要我们将需要的宏进行加上就可以了 在以下的位置 项目 gt 属性 gt 配置属性 gt C C gt 预处理器 gt 预处理器定义 增加 CRT SECURE NO DEPRECATE 完成

  • QTreeWidget存放自定义数据

    QTreeWidget 双击可编辑的设置 connect ui treeWidget RedLamp SIGNAL itemClicked QTreeWidgetItem int this SLOT Slot TreeRedLampIncr

  • C++中类的静态变量在哪初始化

    C 中类的静态变量在哪初始化 static修饰的成员变量存在哪 static成员变量 不能在头文件中初始化 3 static成员必须在类外初始化 并且 不能在头文件中初始化 否则 在链接时可能会出现重定义的问题 C 成员初始化 class

随机推荐

  • C++ 强制转换运算符

    强制转换运算符是一种特殊的运算符 它把一种数据类型转换为另一种数据类型 强制转换运算符是一元运算符 它的优先级与其他一元运算符相同 大多数的 C 编译器都支持大部分通用的强制转换运算符 type expression 其中 type 是转换

  • 【Unity Shader】浅析Unity shader中RenderType的作用及_CameraDepthNormalsTexture

    初学Unity ShaderLab的时候 一定有接触过Unity Shader中的Tags标签块 比如 span span LightMode Vertex Queue Transparent IgnoreProjector True Re

  • stm32第二课

    stm编程写状态机 使用MENU 菜单 设置多个变量 c文件是驱动文件 h文件是库文件豆腐线规范 并做读书笔记 AHB总线规范是AMBA总线规范的一部分 AMBA总线规范是ARM公司提出的总线规范 被大多数SoC设计采用 它规定了AHB A

  • 函数的引用返回

    引用是给变量取一个别名 所以引用传递会直接进行变量本身的传递 它的最大好处是可以把别处对变量的改变保留下来 第二好处是它提高了性能 如果函数的返回值是一个引用 那么 如上文所说 它会节约一组构造 赋值和析构过程 但是 函数返回引用往往会带来

  • ZooKeeper的学习与应用

    转载 http blog csdn net rengq126 article details 7393227 最近大概学习了一下ZooKeeper 本身并没有深入 LGG尝试着在虚拟机里面搭了平台 看了看一些教材 从网上到处看别人的博文并引

  • Amdahl's law and Gustafson's law

    在高并发程序设计中有两个非常重要的定律 Amdahl 阿姆达尔定律 Gustafson定律 古斯塔夫森定律 这两个定律从不同的角度诠释了加速比与系统串行化程度 cpu核心数之间的关系 它们是我们在做高并发程序设计时的理论依据 加速比 加速比

  • python学习之定制发送带附件的电子邮件

    Python SMTP发送邮件 SMTP Simple Mail Transfer Protocol 即简单邮件传输协议 它是一组用于由源地址到目的地址传送邮件的规则 由它来控制信件的中转方式 python的smtplib提供了一种很方便的

  • 【C++】STL-常用算法-常用查找算法

    0 前言 1 find include

  • @ResponseBody 和 @RequestBody以及@PathVariable的作用

    一 ResponseBody ResponseBody是作用在方法上的 ResponseBody 表示该方法的返回结果直接写入 HTTP response body 中 一般在异步获取数据时使用 也就是AJAX 在使用 RequestMap

  • form表单及ajax使用form-serialize提交

    1 表单定义 在网页中 表单主要负责数据的采集功能 表单由 表单标签 表单域 表单按钮 组成 html的form标签就是表单标签 是一个容器 用来将页面中指定的区域划定为表单区域 表单域 提供了采集用户信息的渠道 input textare

  • 计算机毕业设计-基于SSM的学生成绩管理系统

    项目摘要 系统开发技术 Java语言 Java主要采用CORBA技术和安全模型 可以在互联网应用的数据保护 它还提供了对EJB Enterprise JavaBeans 的全面支持 java servlet API Java java se

  • 微信小程序自定义导航栏

    微信小程序自定义导航栏 业务需求 点击小房子进行跳转指定的页面 更改小房子的样式 或者是自定义导航栏 首先我们需要找到pages json这个文件 如果是原生的微信小程序文件名字是 app json其实就是找到配置路由的文件 在代码里面添加

  • 服务器拖两个屏幕win10系统,win10系统设置两个显示器的还原方案

    win10系统使用久了 好多网友反馈说关于对win10系统设置两个显示器设置的方法 在使用win10系统的过程中经常不知道如何去对win10系统设置两个显示器进行设置 有什么好的办法去设置win10系统设置两个显示器呢 在这里小编教你只需要

  • Jackson 双引号的问题

    当用执行下面的代码的时候 String json name chenhailong Map

  • 手机端效果实现下拉刷新上拉加载更多数据---自定义数据篇

    代码如下 需安装react pullload插件 yarn add react pullload import React from react import node modules react pullload dist ReactPu

  • Libvrit热添加/删除CPU/MEM

    默认用virt manager创建的虚拟机不能直接动态添加删除CPU 需要先修改配置 关闭虚拟机后再开启生效 virsh setvcpus client1043 8 config maximum 然后关闭虚拟机后 再开机就可以随意热添加删除

  • 【博客698】为什么当linux作为router使用时，安装docker后流量转发失败

    为什么当linux作为router使用时 安装docker后流量转发失败 场景 当一台linux机器作为其它服务器的router 负责转发流量的时候 让你在linux上安装docker之后 就会出现流量都被drop掉了 原因 没装docke

  • 卷积操作代码举例————PyTorch

    哔哩大学的PyTorch深度学习快速入门教程 绝对通俗易懂 小土堆 的P17讲讲述了卷积操作的举例使用 首先 要做的效果如图 一个很简单的输入图像 卷积核首先和输入图像左上角33对齐 然后对应格子相乘 再9个格子相加 即1 22 0 1 如

  • MATLAB BP神经网络预测算法

    内容 BP神经网络是一种多层前馈网络 可以进行学习和存储输入输出映射关系 不需要建立数学方程式 BP神经网络预测算法预测序号15的跳高成绩 下表是国内男子跳高运动员各项素质指标 P 3 2 3 2 3 3 2 3 2 3 4 3 2 3 3

  • [洛谷] [NOIP2018 提高组] 旅行 加强版 - 基环树

    题目链接 https www luogu com cn problem P5049 题目描述 小 Y 是一个爱好旅行的 OIer 她来到 X 国 打算将各个城市都玩一遍 小Y了解到 X国的 n 个城市之间有 m 条双向道路 每条双向道路连接

热门标签