「学习笔记」欧拉回路

定义

设 (G(V,E)) 是一张图
欧拉回路 : 图 (G) 中经过每条边一次并且仅一次的回路.
欧拉路径 : 图 (G) 中经过每条边一次并且仅一次的路径.
欧拉图 : 存在欧拉回路的图.
半欧拉图 : 存在欧拉路径但不存在欧拉回路的图.

定理与性质

以下的图中, 默认把孤立点删除, 因为这样不会影响原图是否为欧拉图.

定理1 : 无向图 (G) 为欧拉图, 当且仅当 (G) 为连通图且所有顶点的的度为偶数.
推论1 : 无向图 (G) 为半欧拉图, 当且仅当 (G) 为连通图, 且除了两个顶点的度为奇数外, 其他顶点的度为偶数.

定理2 : 有向图 (G) 为欧拉图, 当且仅当 (G) 为连通图且所有顶点的入度等于出度.
推论2 : 有线图 (G) 为半欧拉图, 当且仅当 (G) 为连通图, 且存在顶点 (u) 的出度比入度大 (1), 顶点 (v) 的入读比出度大 (1), 其他顶点的入度等于出度.

性质1 : 设 (C) 是欧拉图 (G) 的一个简单回路, 将 (C) 中的边从图 (G) 中删去得到一个新图 (G'), 则 (G') 的每一个极大连通子图都存在一条欧拉回路.

性质2 :　设 (C_1,C_2) 是图 (G) 的两个没有公共边, 但有至少一个公共点的简单回路, 则可以将它们合并成一个新的简单回路 (C').

求欧拉回路

过程

(dfs), 当一个点的所有边都被遍历过后, 将这个点加入答案的栈中, 最后从栈顶开始输出答案.

其实这个算法叫做 Hierholzer 算法, 它的想法是每次找出一条回路, 然后从图上删去这个回路, 再从回路上的每个节点开始去找新的回路, 找到新的回路后再把它和原来的回路合并. 根据上面的性质1 和性质2, 可以证明若图上存在一条欧拉回路, 这样一定能够找出来.

而上述的过程其实就相当于对整张图 (dfs) 一遍, 每次 (dfs) 到顶时就相当于找到了一条回路. 假设这条回路上存在一条边 ((u,v)), 那么沿着 ((u,v')) 继续 (dfs) 就相当于找一条新的回路. 一个点的所有边都被遍历过后再把这个点加入栈中, 就相当于合并若干个环.

代码

欧拉回路
这个板子相对麻烦一点, 因为它要同时处理有向图和无向图的情况, 并且要求输出边的方案.

#include<bits/stdc++.h>

using namespace std;

const int _=1e5+7;
const int __=4e5+7;

int n,m,ty,st,de[_][2];
int lst[_],nxt[__],to[__],id[__],tot=1;
int ans[__],top;
bool ban[__];

int gi(){
	int x=0; char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9'){ x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }
	return x;
}

void Add(int x,int y,int t,int ty){
	nxt[++tot]=lst[x]; to[tot]=y; id[tot]=t; lst[x]=tot;
	if(ty==1){ nxt[++tot]=lst[y]; to[tot]=x; id[tot]=-t; lst[y]=tot; }
}

void Init(){
	ty=gi(),n=gi(),m=gi();
	int x,y;
	for(int i=1;i<=m;i++){
		x=gi(),y=gi();
		Add(x,y,i,ty);
		if(ty==1) de[x][0]++,de[y][0]++;
		else de[x][1]++,de[y][0]++;
	}
}

void Dfs(int u,int t){
	while(lst[u]){
		int i=lst[u];
		if(ban[i]){ lst[u]=nxt[i]; continue; }           // 需要及时更新 lst, 否则会被卡到 m^2
		ban[i]=1;
		if(ty==1) ban[i^1]=1;
		lst[u]=nxt[i];
		Dfs(to[i],t+1);
		ans[++top]=id[i];
	}
}

void Run(){
	for(int i=1;i<=n;i++)
		if(ty==1&&de[i][0]%2){ puts("NO"); return; }
		else if(ty==2&&de[i][0]!=de[i][1]){ puts("NO"); return; }
	for(int i=1;i<=n;i++)
		if(de[i][0]){ st=i; break; }
	Dfs(st,1);
	for(int i=2;i<=tot;i++)
		if(!ban[i]){ puts("NO"); return; }
	puts("YES");
	for(int i=m;i>=1;i--)
		printf("%d ",ans[i]);
	putchar('
');
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("x.in","r",stdin);
	//freopen("x.out","w",stdout);
#endif
	Init();
	Run();
	return 0;
}