【学习笔记】欧拉回路
前言
震惊！某位正在准备JXOI2019的蒟蒻竟然连欧拉回路都不会
于是他就开始学
定义
度数：有向图中，出度和入度分别指一个点的出边和入边的条数；无向图中则指一个点所连边数
奇点：度数为奇数的点
欧拉路径：如果图G中的一个路径包括每一条边恰好一次(每条边经过一次)，则该路径为欧拉路径
欧拉回路：一条欧拉路径的起点和终点为同一点；或理解为一个回路为欧拉路径则这条路径为欧拉回路
欧拉图：有欧拉回路的图
判断（充要条件）
无向图存在欧拉路径：除两个奇点(起点终点)外，其他点的度数均为偶数
有向图存在欧拉路径：起点出度=入度+1，终点入度=出度+1，其他路径上的点的出度=入度
无向图存在欧拉回路：当且仅当所有顶点度数为偶数，且为连通图
有向图存在欧拉回路：所有顶点的出度=入度且为连通图
算法
Fluery算法（没学）
Hierholzer算法
此算法可以找欧拉回路，而在找不到欧拉回路时会找欧拉路径
针对无向图的算法流程
void Hierholzer(int x)
{
for(x所连到的点y)
{
删除边(x,y)
删除边(y,x)
Hierholzer(y);
}
将x压入答案栈
}
将栈顶元素依次弹出输出即可得到欧拉回路/路径
我还没碰到有向图求欧拉回路的题目，暂时猜想针对有向图只需删去”删除边（y,x）”
思考1：
为什么不能写成
void Hierholzer(int x)
{
输出x
for(x所连到的点y)
{
删除边(x,y)
删除边(y,x)
Hierholzer(y);
}
}
此算法又称圈套圈算法，如果所给图为两个相连的环的话，可能会先跑完其中一个环，直接输出了其中的一个环上的路径
思考2：
在只要求输出路径，而不要求路径顺序（指无向图，有向图一定不能这样）的时候把“将x压入答案栈”改成“输出x”也可以吗？
我以为是可以的，但是在写完下面的例题1后我发现我似乎不能解决这个问题，但暂时未举出不可以的反例
tip：为了更方便地删边，当点数不多时，我们可以用邻接矩阵存图，删边时直接\(G[x][y]\)–
由于涉及欧拉回路的题目较少，讲解较少，推荐读者结合例题理解欧拉回路
比较
听说后者编程复杂度和时间复杂度都优于前者，但是前者应用广泛性好
例题
T1
分析
此题要求求出无向图的欧拉路径/回路
当然这类题一般都会叫你输出字典序最小的答案
针对这道题考虑几个细节：
1.顶点从1~500编号，但它并没有保证输入给的顶点编号连续（如告诉你1-2，2-5，5-6），
所以我用mn存下给出点的最小值，用mx存下给出点的最大值，用v[x]表示x点是否在输入给出
2.虽然输入数据保证至少又一个解，
但我的代码中还是写了一个并查集判断连通性（这也是存在欧拉回路的必要条件）
3.我针对是否存在欧拉回路分类，记下了每个点的度deg[x]，如果有deg[x]&1=1即deg[x]为奇数则说明有奇点，我将从最小的奇点往下搜，
如果没有deg[x]&1=1则说明有欧拉回路，我从所给最小点往下搜
（当然我这里偷了个懒，题目说输入保证有解所以我直接考虑欧拉路径是不是欧拉回路，如果不保证输入有解，即还需判断是否有欧拉路径，则需在并查集判断连通性的基础上再看是否仅存在两个奇点）
4.要输出字典序最小解，则需要注意在dfs时从可连到的最小点往下搜
代码
Talk is cheap,show you the code.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
using namespace std;
const int N=505;
const int M=1050;
const int inf=0x7fffffff;
int m;
int mn=inf,mx=-inf;
int deg[N];
int G[N][N];
stack <int> s;
int f[N];bool v[N];
int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
void merge(int x,int y)
{
int fx=getf(x);
int fy=getf(y);
if(fx!=fy) f[fx]=fy;
}
void Hierholzer(int x)
{
for(int i=mn;i<=mx;i++)
if(G[x][i])
{
G[x][i]--;
G[i][x]--;
Hierholzer(i);
}
s.push(x);
}
int main()
{
for(int i=1;i<=500;i++) f[i]=i;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
G[x][y]++;
G[y][x]++;
deg[x]++;deg[y]++;
v[x]=1;v[y]=1;
merge(x,y);
mn=min(mn,x);
mn=min(mn,y);
mx=max(mx,x);
mx=max(mx,y);
}
for(int i=mn;i<=mx;i++)
for(int j=mn;j<=mx;j++)
if(v[i]&&v[j]&&getf(i)!=getf(j))
{
printf("No Solution!\n");
return 0;
}
for(int i=mn;i<=mx;i++)
if(v[i]&&(deg[i]&1))
{
Hierholzer(i);//找欧拉路径
break;
}
else if(i==mx) Hierholzer(mn);//从最小点找欧拉回路
while(!s.empty())
{
printf("%d\n",s.top());
s.pop();
}
return 0;
}
其他想法：（只是我个人学习过程中的思考，只想简单知道这个算法怎么写的可以跳过）
上面的思考2中，我认为在只要求输出路径，而不要求路径顺序（指无向图，有向图一定不能这样）的时候把“将x压入答案栈”可以改成“输出x”
因为我思考了这样一个例子（参考博客所给）（按本题输入格式）
8
1 2
2 3
3 4
4 5
5 6
6 3
3 7
7 1
那么我不用栈，在不改变起点（此例中为1）的情况下，将
void Hierholzer(int x)
{
for(int i=mn;i<=mx;i++)
if(G[x][i])
{
G[x][i]--;
G[i][x]--;
Hierholzer(i);
}
s.push(x);
}
改成
void Hierholzer(int x)
{
for(int i=mx;i>=mn;i--)
if(G[x][i])
{
G[x][i]--;
G[i][x]--;
Hierholzer(i);
}
printf("%d\n",x);
}
输出了同一正确答案：1 2 3 4 5 6 3 7 1
但是，这种改法连洛谷所给样例都过不了（交上去也仅能A一个点）
为什么？
我们来分析一下，先从这个过不去的样例入手
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6
其实不用，这个就行
2
1 2
2 3
改之后会输出：3 2 1
显然一条链的情况它就会出问题
那么我继续想，对于不是回路的欧拉路径，它只要搜到了路径终点，就会直接输出而出错，那么如果是欧拉回路的话这样可以吗？
抱歉，由于我太菜了，这个问题暂时不能解决，目前找不出能hack的欧拉回路数据，这种改法能过洛谷的第一个测试点，而经测试，剩余九个点都是欧拉路径而非回路，所以希望想思考这个问题的读者能帮我这个蒟蒻解决它
T2
分析
这题把“无序字母对”当做边，字母当作点
就是求无向图欧拉路径
相对上题，只是多了一个判断是否存在欧拉路径而已
注意怎么把不同字母映射到不同数字上就可以
代码
Talk is cheap,show you the code.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
using namespace std;
const int N=26*2+5;
const int M=26*26+5;
const int inf=0x7fffffff;
int m;
int mx=-inf,mn=inf;
int G[N][N];
stack <int> sta;
int deg[N];
int f[N];
int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
void merge(int x,int y)
{
int fx=getf(x);
int fy=getf(y);
if(fx!=fy) f[fx]=fy;
}
int F(char c)
{
if('A'<=c&&c<='Z') return int(c-'A'+1);
if('a'<=c&&c<='z') return int(c-'a'+27);
}
char FF(int x)
{
if(1<=x&&x<=26) return char('A'+x-1);
if(27<=x&&x<=52) return char('a'+x-27);
}
void Hierholzer(int x)
{
for(int i=mn;i<=mx;i++)
if(G[x][i])
{
G[x][i]--;
G[i][x]--;
Hierholzer(i);
}
sta.push(x);
}
char s[5];
int main()
{
for(int i=1;i<=26*2;i++) f[i]=i;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",s);
int x=F(s[0]),y=F(s[1]);
merge(x,y);
G[x][y]++;G[y][x]++;
deg[x]++;deg[y]++;
mx=max(mx,x);
mx=max(mx,y);
mn=min(mn,x);
mn=min(mn,y);
}
for(int i=mn;i<=mx;i++)
for(int j=mn;j<=mx;j++)
if(deg[i]&°[j]&&getf(i)!=getf(j))//别忘了加条件deg[i]&°[j]
{
printf("No Solution\n");
return 0;
}
int cnt=0;//奇点个数
for(int i=mn;i<=mx;i++) if(deg[i]&1) cnt++;
if(cnt==0||cnt==2)
{
for(int i=mn;i<=mx;i++)
if(deg[i]&1)
{
Hierholzer(i);
break;
}
else if(i==mx) Hierholzer(mn);
while(!sta.empty())
{
printf("%c",FF(sta.top()));
sta.pop();
}
}
else printf("No Solution\n");
return 0;
}
本人太菜QAQ，如果有错误请指出哦QAQ
2019.3.30