图论知识——欧拉回路(一笔画问题) Hierholzer方法

2023-11-10 16:41

本文主要是介绍图论知识——欧拉回路(一笔画问题) Hierholzer方法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

许多题目看起来是模拟,其实应该抽象为数学模型,寻找效率更高的解题方法
前置知识
欧拉回路不等于欧拉路径,AB BC CA构成欧拉环路ABCA,符合题意。AB BC CD构成欧拉路径ABCD,也符合题意。
https://blog.csdn.net/qq_34454069/article/details/77779300
https://blog.csdn.net/qq632544991p/article/details/51097077
题目:https://www.luogu.org/problemnew/show/P1341
题解
https://blog.csdn.net/stillxjy/article/details/51956183
https://blog.csdn.net/binling/article/details/51742845
https://blog.csdn.net/binling/article/details/51742845
Hierholzer :
在本题中,n个无序字母对构成n+1长度的欧拉回路或欧拉字母对,那么只要通过度来判定是欧拉回路或者欧拉路径,那么只要找到起始点就一定可以简单的通过DFS找出该路径。
写法一:

#include<bits/stdc++.h>
using namespace std;
int a[106],c[10006],du[101],n,x,y,k,t,tot=0;
bool b[106][106];
char s[2];
void dfs(int u){for(int i=0;i<58;i++)if(b[u][i]){b[u][i]=b[i][u]=0;//删边 dfs(i);}c[++tot]=u;//递归退栈时存储,所以顺序是反的,也可以用栈 
}
int main(){cin>>n;k=0xfffffff;//重要赋值 for(int i=1;i<=n;i++){cin>>s;x=s[0]-'A'; y=s[1]-'A';//节省空间 k=min(k,min(x,y));b[x][y]=b[y][x]=1;//无向图标记路径 du[x]++;du[y]++;//计算度 }for(int i=0;i<58;i++)if(du[i]&1) a[++a[0]]=i;//计算度是奇数的点,并保存 if(a[0]==0) dfs(k);//题目要求输出字典序最小的方案 
//没有度为奇数的点 ,这是欧拉环路的情况 else if(a[0]==2) dfs(a[1]);//第一个度为奇数的点是端点 
//度为奇数的点为两个,这两个是两端的端点,这是欧拉路径的情况else{cout<<"No Solution\n";return 0;//必须有这个返回 }for(int i=tot;i>=1;i--) printf("%c",c[i]+'A');//for(int i=tot;i>=1;i--) cout<<c[i]+'A';//输出不规范,要用格式化输出return 0;
}

在这里插入图片描述
写法二:

#include<bits/stdc++.h>
using namespace std;
int n,x,y,k,i,ss=0;
bool b[106][106];
char s[2];
int cnt[106]={0};
stack<int> c;
void dfs(int u){for(int i=0;i<58;i++)if(b[u][i]){b[u][i]=b[i][u]=0;//删边 dfs(i);}c.push(u);//递归退栈时存储,所以顺序是反的,也可以用栈 
}
int main(){cin>>n;k=0xfffffff;//重要赋值 vector<int> cnt(106,0);//变长数组的赋值 for(int i=1;i<=n;i++){cin>>s;x=s[0]-'A'; y=s[1]-'A';//节省空间 k=min(k,min(x,y));b[x][y]=b[y][x]=1;//无向图标记路径 cnt[x]^=1;cnt[y]^=1;
//利用异或运算,同0异1,运算偶数次是0,运算奇数次是1 }for(i=0;i<106;i++) if(cnt[i]) ss++; 
//要对所有的点进行遍历,ss是度为奇数的点的个数 if(ss&&ss!=2){
//条件取反:ss=0||s=2,即欧拉回路的情况和欧拉路径的情况 cout<<"No Solution\n";return 0;//必须有这个返回 }for(i=0;i<106;i++)if(cnt[i]) break; if(i==106) dfs(k);
//没有度为奇数的点,及该情况是欧拉回路 ,k保证最小字典序 else dfs(i); //该情况是欧拉路径 ,也能保证最小字典序 while(!c.empty()){printf("%c",c.top()+'A');c.pop();}cout<<endl;return 0;
}

在这里插入图片描述

这篇关于图论知识——欧拉回路(一笔画问题) Hierholzer方法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/qq_38993096/article/details/87897254
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/383959

相关文章

Nginx启动失败:端口80被占用问题的解决方案

《Nginx启动失败:端口80被占用问题的解决方案》在Linux服务器上部署Nginx时,可能会遇到Nginx启动失败的情况,尤其是错误提示bind()to0.0.0.0:80failed,这种问题通... 目录引言问题描述问题分析解决方案1. 检查占用端口 80 的进程使用 netstat 命令使用 ss

Python使用Pandas对比两列数据取最大值的五种方法

《Python使用Pandas对比两列数据取最大值的五种方法》本文主要介绍使用Pandas对比两列数据取最大值的五种方法,包括使用max方法、apply方法结合lambda函数、函数、clip方法、w... 目录引言一、使用max方法二、使用apply方法结合lambda函数三、使用np.maximum函数

Qt 中集成mqtt协议的使用方法

《Qt中集成mqtt协议的使用方法》文章介绍了如何在工程中引入qmqtt库,并通过声明一个单例类来暴露订阅到的主题数据,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友一起看看吧... 目录一,引入qmqtt 库二,使用一,引入qmqtt 库我是将整个头文件/源文件都添加到了工程中进行编译,这样 跨平台

Nginx设置连接超时并进行测试的方法步骤

《Nginx设置连接超时并进行测试的方法步骤》在高并发场景下,如果客户端与服务器的连接长时间未响应,会占用大量的系统资源,影响其他正常请求的处理效率,为了解决这个问题,可以通过设置Nginx的连接... 目录设置连接超时目的操作步骤测试连接超时测试方法:总结:设置连接超时目的设置客户端与服务器之间的连接

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D

Python使用国内镜像加速pip安装的方法讲解

《Python使用国内镜像加速pip安装的方法讲解》在Python开发中,pip是一个非常重要的工具,用于安装和管理Python的第三方库,然而,在国内使用pip安装依赖时,往往会因为网络问题而导致速... 目录一、pip 工具简介1. 什么是 pip?2. 什么是 -i 参数?二、国内镜像源的选择三、如何

IDEA编译报错“java: 常量字符串过长”的原因及解决方法

《IDEA编译报错“java:常量字符串过长”的原因及解决方法》今天在开发过程中,由于尝试将一个文件的Base64字符串设置为常量,结果导致IDEA编译的时候出现了如下报错java:常量字符串过长,... 目录一、问题描述二、问题原因2.1 理论角度2.2 源码角度三、解决方案解决方案①:StringBui

Linux使用nload监控网络流量的方法

《Linux使用nload监控网络流量的方法》Linux中的nload命令是一个用于实时监控网络流量的工具,它提供了传入和传出流量的可视化表示,帮助用户一目了然地了解网络活动,本文给大家介绍了Linu... 目录简介安装示例用法基础用法指定网络接口限制显示特定流量类型指定刷新率设置流量速率的显示单位监控多个

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下:需要在

JavaScript中的reduce方法执行过程、使用场景及进阶用法

《JavaScript中的reduce方法执行过程、使用场景及进阶用法》:本文主要介绍JavaScript中的reduce方法执行过程、使用场景及进阶用法的相关资料,reduce是JavaScri... 目录1. 什么是reduce2. reduce语法2.1 语法2.2 参数说明3. reduce执行过程