图论知识——欧拉回路(一笔画问题) 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方法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/383959

相关文章

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

sqlite3 相关知识

WAL 模式 VS 回滚模式 特性WAL 模式回滚模式(Rollback Journal)定义使用写前日志来记录变更。使用回滚日志来记录事务的所有修改。特点更高的并发性和性能;支持多读者和单写者。支持安全的事务回滚,但并发性较低。性能写入性能更好,尤其是读多写少的场景。写操作会造成较大的性能开销,尤其是在事务开始时。写入流程数据首先写入 WAL 文件,然后才从 WAL 刷新到主数据库。数据在开始

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

webm怎么转换成mp4?这几种方法超多人在用!

webm怎么转换成mp4?WebM作为一种新兴的视频编码格式,近年来逐渐进入大众视野,其背后承载着诸多优势,但同时也伴随着不容忽视的局限性,首要挑战在于其兼容性边界,尽管WebM已广泛适应于众多网站与软件平台,但在特定应用环境或老旧设备上,其兼容难题依旧凸显,为用户体验带来不便,再者,WebM格式的非普适性也体现在编辑流程上,由于它并非行业内的通用标准,编辑过程中可能会遭遇格式不兼容的障碍,导致操

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验