欧拉路径

2024-03-30 21:24:03

貌似很多博客都喜欢用一笔画来引入欧拉路径，但像您这样的强者时无需那些繁琐的东西，我们直接进入正题。

定义：

图中经过所有边恰好一次的路径叫做欧拉路径。

如果起点和终点一样，那它就是欧拉回路。

判定：

~~判定当前图中是否存在欧拉路径其实比寻找更麻烦~~

显然，欧拉回路也是欧拉路径，但为了方便区分，下文判定中的欧拉路径特指起点和终点不同。

判定方法：

首先，当且仅当这张图将有向边视为无向边时联通。

有向图欧拉路径：图中恰好存在一个点（起点）出度比入度多1，恰好一个点（终点）入度比出度多1，剩下所有点入度等于出度。
有向图欧拉回路：图中所有点入度等于出度（任一点都可以做起点和终点）。
无向图欧拉路径：图中恰好有两个点的度数为奇数（起点和终点），其他所有点的度数为偶数。
无向图欧拉回路：图中所有点的度数都为偶数（任一点都可以做起点和终点）。

寻找：

算法一：Fluery 算法。时间复杂度 \(O(m^2)\)，不常用。

算法二：Hierholzer 算法。时间复杂度 \(O(m)\)，常用。

只写 Hierholzer 算法，做法非常简单。

从起点开始 dfs，标记选了的边不能重复选，这里用类似Dinic的当前弧优化。
当前点不存在出边时回退，并将当前点入栈 \(P\)。
当dfs结束时倒序输出栈 \(P\) 中的节点即可。

算法导论上似乎有该算法证明。

例题：

P7771 【模板】欧拉路径

题目保证联通，所以直接判断入度和出度即可。

要求字典序最小，那么每次都要选能到达的最小的点。

可以将边离线下来按 \(v\) 从大到小排序，然后依次插入到链式前向星里，这样可以保证每次选到的都是最小的。

当前弧优化不加复杂度就假了。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
inline int read(){
	int p=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
	return p*f;
}
const int N=1e5+5;
const int M=2e5+5;
int n,m;
struct edge{
	int v,nxt;
}e[M];
int head[N],en;
inline void insert(int u,int v){
	e[++en].v=v;
	e[en].nxt=head[u];
	head[u]=en;
}
struct QWQ{
	int u,v;
}E[M];
inline bool cmp(QWQ a,QWQ b){
	return a.v>b.v;
}
int p[M],pn;
void dfs(int u){
	for(int i=head[u];i;i=head[u]){
		int v=e[i].v;
		head[u]=e[i].nxt;
		dfs(v);
	}
	p[++pn]=u;
}
int flagin,flagout,flag;
int ind[N],outd[N];
int S=1;
signed main(){
	n=in,m=in;
	for(int i=1;i<=m;i++)
		E[i].u=in,E[i].v=in,
		outd[E[i].u]++,ind[E[i].v]++;
	sort(E+1,E+1+m,cmp);
	for(int i=1;i<=m;i++)
		insert(E[i].u,E[i].v);
	for(int i=1;i<=n;i++){
		if(ind[i]!=outd[i])flag++;
		if(ind[i]==outd[i]+1)flagout++;
		if(ind[i]+1==outd[i])flagin++,S=i;
	}
	if(flag==0||(flag==2&&flagout==1&&flagin==1)){
		dfs(S);
		for(int i=pn;i>=1;i--)
			cout<<p[i]<<' ';		
	}
	else cout<<"No";
	return 0;
}

练习：

P1127

将每个字母视为点，单词视为边，就和上面差不多了，注意欧拉路径的起始点。

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+5;
int n;
string s[N];
int len[N];
struct edge{
	int v,o,nxt;
}e[N];
int head[30],en;
inline void insert(int u,int v,int o){
	e[++en].v=v;
	e[en].o=o;
	e[en].nxt=head[u];
	head[u]=en;
}
struct QWQ{
	int u,v,o;
	string s;
}E[N];
bool cmp(QWQ a,QWQ b){
	return a.s>b.s;
}
int in[30],out[30];
int flagin,flagout,flag;
int S;
int mp[N][N];
int p[N],pn;
void dfs(int u){
	for(int i=head[u];i;i=head[u]){
		int v=e[i].v,o=e[i].o;
		head[u]=e[i].nxt;
		dfs(v);
		p[++pn]=o;
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>s[i],len[i]=s[i].length(),
		E[i].u=s[i][0]-'a'+1,E[i].v=s[i][len[i]-1]-'a'+1,E[i].s=s[i],E[i].o=i,
		out[s[i][0]-'a'+1]++,in[s[i][len[i]-1]-'a'+1]++;		
	for(int i=1;i<=26;i++){
		if(out[i]!=in[i])flag++;
		if(out[i]==in[i]+1)flagout++,S=i;
		if(out[i]+1==in[i])flagin++;
	}
	if(!flag) for(int i=1;i<=26;i++)
			if(in[i]){S=i;break;}
	if(!flag||(flag==2&&flagout==1&&flagin==1)){
		sort(E+1,E+1+n,cmp);
		for(int i=1;i<=n;i++)
			insert(E[i].u,E[i].v,E[i].o);
		dfs(S);
		if(pn!=n)cout<<"***";
		else{
			for(int i=pn;i>=1;i--)
				cout<<s[p[i]]<<"."[i==1];
		}
	}
	else{
		cout<<"***";
	}
	return 0;
}

P2731

变成了无向图，一样搞搞就过了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
inline int read(){
	int p=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
	return p*f;
}
const int N=505;
const int M=1100;
int m;
struct edge{
	int v,o,nxt;
}e[M<<1];
int head[N],en;
inline void insert(int u,int v,int o){
	e[++en].v=v;
	e[en].o=o;
	e[en].nxt=head[u];
	head[u]=en;
}
struct llmmkk{
	int u,v,o;
}E[M<<1];
inline bool cmp(llmmkk AK,llmmkk IOI){
	return AK.v>IOI.v;
}
int vis[M];
int d[N];
int p[M],pn;
void dfs(int u){
	for(int i=head[u];i;i=head[u]){
		int v,o=e[i].o;head[u]=e[i].nxt;
		while(vis[o]&&i){
			i=head[u],o=e[i].o,
			head[u]=e[i].nxt;			
		}
		if(!i)continue;
		v=e[i].v,vis[o]=1;
		dfs(v);
	}
	p[++pn]=u;
}
int n,minn,S;
signed main(){
	m=in;
	for(int i=1;i<=m;i++){
		E[i].u=in,E[i].v=in;
		E[i+m].u=E[i].v,E[i+m].v=E[i].u;
		E[i].o=E[i+m].o=i;
		d[E[i].u]++,d[E[i].v]++;
		n=max(n,max(E[i].u,E[i].v));
	}
	sort(E+1,E+1+(m<<1),cmp);
	for(int i=1;i<=(m<<1);i++)
		insert(E[i].u,E[i].v,E[i].o);	
	for(int i=n;i>=1;i--){
		if(d[i])minn=i;
		if(d[i]&1)S=i;
	}
	if(!S)S=minn;
	dfs(S);
	for(int i=pn;i>=1;i--)
		cout<<p[i]<<'\n';
	return 0;
}

P1341 都差不多

CF547D

这道题还挺有意思的，利用一个 trick，将行和列作为点，从行向列连边代表对应坐标的点，那么如果一个点有偶数条边就一半染红，一半染蓝，如果一个点有奇数条边就考虑连一个超源，因为多出来的边无论哪种颜色都可以。分析行列间每条边会带来的影响，发现超源也一定是偶数条边，所以跑欧拉回路就好了，入边染一个颜色，出边染另一个颜色。

码农公寓

定义：

判定：

寻找：

例题：

练习：

相关文章