【算法】欧拉回路和欧拉路径
Tobiichi_Origami · · 个人记录
欧拉回路和欧拉路径是一种判断一笔画问题的算法，回路是从源点出发后可以遍历过所有的边且经过一次后可以回到原点，路径是从原点出发后遍历所有的边且经过一次后可以到达终点。
- 欧拉回路
实现欧拉回路首先需要判断是否存在欧拉回路。
以上图为例，在因为欧拉回路是重新回到了源点，也说明欧拉回路必须至少有一个环，并且没有一条边会被孤立。所以这也就说明每个点的出度和入度和必须成对，不然绝对会有边遍历不到。
对于无向图来说，也就是度数为偶数。源点的选择也就是它有边连接，因为可能会出现孤立点的情况。
然后就是如何求欧拉回路。其实欧拉回路就是一个爆搜的过程（没有任何技术含量）。
每次枚举每个点的出边，如果这条边没有遍历过就继续搜，无向图需要将正反两条边都干掉，再每次记录走过的边。
还需注意跑完
#include<bits/stdc++.h>
using namespace std;
struct edge{
int to,next;
}ed[1000001];
int he[1000001],idx;
int din[1000001],dout[1000001];
int ans[1000001],cnt;
bool vis[1000001];
int n,m,t;
void insert(int u,int v)
{
ed[idx].to=v;
ed[idx].next=he[u];
he[u]=idx++;
}
void dfs(int u)
{
for(int i=he[u];i!=-1;i=ed[i].next)
{
if(vis[i]) continue;
vis[i]=1;
if(t==1) vis[i^1]=1;//双向
dfs(ed[i].to);
if(t==1) ans[++cnt]=(i>>1)+1;//点的编号
else ans[++cnt]=i+1;
}
}
int main()
{
memset(he,-1,sizeof(he));
scanf("%d %d %d",&t,&n,&m);//1是无向图，2是有向图
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
insert(x,y);
if(t==1) insert(y,x);
din[y]++;dout[x]++;
}
if(t==1)
{
for(int i=1;i<=n;i++)
if((din[i]+dout[i])&1)//度数为偶数
{
puts("NO");
return 0;
}
}
else
{
for(int i=1;i<=n;i++)
if(din[i]!=dout[i])//出度入度成对
{
puts("NO");
return 0;
}
}
for(int i=1;i<=n;i++)
if(he[i]!=-1)//有边连接
{
dfs(i);
break;
}
if(cnt<m)//没有遍历所有的边
{
puts("NO");
return 0;
}
puts("YES");
for(int i=1;i<=cnt;i++) printf("%d ",ans[i]);
return 0;
}- 欧拉路径
首先还是需要判断这个图是否存在欧拉路径。
因为没有求是否最后需要回到源点。所以对于无向图而言，至多有两个点度数可以不为偶数，并且这两个点分别是源点与终点。
有向图也是一样，但还需满足源点只出不进，也就是出度比入度大
和欧拉回路十分相近，只是在判别的时候不太一样，实现方法还是 不会告诉你我不想写无向图了。
#include<bits/stdc++.h>
using namespace std;
struct edge{
int to,next;
}ed[1000001];
struct node{
int u,v;
}a[1000001];
int he[1000001],idx=1;
int din[1000001],dout[1000001];
bool vis[1000001];
int ans[1000001],cnt;
int n,m;
void insert(int u,int v)
{
ed[idx].to=v;
ed[idx].next=he[u];
he[u]=idx++;
}
void dfs(int u)//寻找欧拉路径
{
for(int i=he[u];~i;i=ed[i].next)
if(!vis[i])
{
vis[i]=1;
dfs(ed[i].to);
}
ans[++cnt]=u;
return ;
}
int main()
{
memset(he,-1,sizeof(he));
int s=0,cnta=0,cntb=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
insert(x,y);
din[y]++;dout[x]++;
}
for(int i=1;i<=n;i++)
{
if(din[i]-dout[i]>1||dout[i]-din[i]>1)//有两个以上差相差2的点
{
puts("No");
return 0;
}
if(dout[i]-din[i]==1) cnta++,s=i;//找原点
else if(din[i]-dout[i]==1) cntb++;
}
if(!s)//欧拉回路时
{
for(int i=1;i<=n;i++)
if(!(din[i]+dout[i]&1))
{
s=i;
break;
}
}
if((!cnta&&!cntb)||(cnta==1&&cntb==1))//只有原点和终点或为欧拉回路
{
dfs(s);
for(int i=cnt;i>0;i--) printf("%d ",ans[i]);
}
else puts("No");
return 0;
}题型
1. 与并查集相结合
有时，我们可以不用输出欧拉回路或欧拉路径的具体路径，而是需要求出其他的问题。比如说，在判断欧拉回路时，图有可能不会连通。这时，我们就可用并查集来维护。
以[POI1999]原始生物为例。
题意
给定
思路
我们考虑，如果要使序列最短，就要使每个数对在序列中尽可能有重复的数字，即首尾相连。
提到首尾相连，我们会轻易的想到一个构建一个有向图（因为
因为我们要使每个数对都出现在序列当中，所以抽象到图中即为若干个不连通的连通块，我们可以很轻松的联想到多个不连通的欧拉路径（回路），求用最少的欧拉路径画满整个图与所经过的边数相加。
我们先考虑所经过的边数为多少。显然，即为整个图中的边数。
然后再考虑要用多少笔画完，再欧拉回路和欧拉路径两方面分别考虑。
-
因为在欧拉路径当中，只有一个终点和一个源点，它们至今不出或只出不进，所以出度入度和为奇数。那么每条欧拉路径中有两个奇数点，
n 条欧拉路径中就有2n 个奇数点，整个图中，欧拉路径的个数就是奇数点的个数除以2 吗？显然不是。我们考虑，如果有多条欧拉路径的源点与终点相同，那么源点或终点就应该再算一次，就不应该是奇数点的个数，就应该是入度出度之差的和除以
2 。 -
在欧拉回路当中，有出必有回，所以出度入度之和为偶数。
那这时，我们就可以用到并查集来维护欧拉回路。
我们把每条相连的边并到一个集合当中，即为一个欧拉回路（路径）。遍历这个图中所有的点，如果它是这个集合中的祖先，也就遍历到了一个新集合，且这个集合在之前计算欧拉路径时没有被记录过，那么就代表它所在的集合为一个欧拉回路。直接计入答案。
综上所述，答案即为边的数目加奇数点入度出度之差的和除以
#include<bits/stdc++.h>
using namespace std;
int f[100001];
int din[100001],dout[100001];
bool vis[100001],is[100001];
map<pair<int,int>,int>mp;
int n,m,sum,ans,rep;
int find(int x)
{
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void merge(int x,int y)
{
int p=find(x),q=find(y);
if(p!=q) f[q]=p;
}
int main()
{
for(int i=1;i<=1000;i++) f[i]=i;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
if(!mp.count({x,y}))
{
n=max(n,max(x,y));
merge(x,y);
is[x]=is[y]=1;
din[y]++;dout[x]++;
}
else rep++;
}
for(int i=1;i<=n;i++)
if((din[i]-dout[i])!=0)
vis[find(i)]=1,sum+=abs(din[i]-dout[i]);
for(int i=1;i<=n;i++)
if(!vis[i]&&f[i]==i&&is[i])
ans++;
printf("%d",m+(sum>>1)+ans-rep);
return 0;
}总结
当一个有向图不为欧拉图时，我们最少需要奇数点入度出度之差的和除以
当推广到无向图时，就为度数为奇数点的个数除以
习题
单词游戏 直接用并查集判连通即可
Ant Trip 直接引用结论即可
相框 结论的逆运用