欧拉图

---

欧拉图的定义

经过图中所有边，且每条边只经过一次的路径叫欧拉路径。

经过图中所有边，且每条边只经过一次的回路叫欧拉回路。

有欧拉回路的图叫欧拉图，有欧拉路径但没有回路的叫半欧拉图。

---

欧拉定理

如果一个图是欧拉图：

定理一：无向图为连通图且所有节点的度为偶数。

定理二：有向图的基图联通，且所有点的出度等于入度。

如果一个图是欧拉图：

定理一：无向图的起点和终点都是该图中唯一度数为奇数的点。

定理二：有向图的起点是该图仅有的一个出度比入度多一的点，终点是图仅有的一个入度比出度多一的点。

---

Hierholzer算法求欧拉路径

前提：已经知道该图为欧拉图（或半欧拉图）。

算法步骤：

1.确定起点：欧拉图可随意确定一个起点，有向半欧拉图需要一出度比入度多一的那个点作为起点，无向半欧拉图需要以任意一个奇数节点为起点。

2.删边：删除走过的边（点可以走多次但边不能）。

3.没有相连边的点入栈：一个节点变成独立的节点时，入栈。

4.最后输出栈内元素：这就是一个欧拉图的一种欧拉路径。

代码模板：

void dfs(int u){
	for(int i=l;i<=r;i++){
		if(g[u][i]){
			g[u][i]--;
			g[i][u]--;
			dfs(i);
		}
	}
	s.push(u); 
}

#include<iostream>
#include<stack>
using namespace std;
int n,m,g[101][101],node[101],cnt,k;
stack<int> s;
void dfs(int u){
	for(int i=1;i<=n;i++){
		if(g[u][i]){
			g[u][i]--;
			g[i][u]--;
			dfs(i);
		}
	}
	s.push(u); 
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		g[u][v]++,g[v][u]++;
		node[u]++,node[v]++;
	}
	for(int i=1;i<=n;i++){
		if(node[i]&1==1){
			cnt++;
			k=i;
		}
	}
	if(cnt==2){
		dfs(k);
		while(!s.empty()){
			cout<<s.top()<<" ";
			s.pop();
		}
	}else if(cnt==0){
		dfs(1);
		while(!s.empty()){
			cout<<s.top()<<" ";
			s.pop();
		}
	}else cout<<"It isn't eulerian!";
}

---

例题：

A.欧拉回路

这道题貌似模板，只要知道欧拉图的性质就行了，既所有点的度数为偶数。于是就有了下面这一段代码：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int n,m,a[1001];
int main(){
	while(cin>>n){
		if(n==0)return 0;
		cin>>m;
		memset(a,0,sizeof(a));
		int cnt=0;
		bool flag=true;
		for(int i=1;i<=m;i++){
			int u,v;
			cin>>u>>v;
			a[u]++,a[v]++;
		}
		for(int i=1;i<=n;i++){
			if(a[i]%2==1||a[i]==0){
				flag=false;
				break;
			}
		}
		if(flag==false)cout<<"0\n";
		else cout<<"1\n";
	}
} 

然后交上去就会发现90wa。

因为题目并没有说给出的图一定是连通图。

正确思路：

先从第一个节点开始深搜遍历，遍历到的点就标记起来，如果有没标记过的点，那么这个图就是非连通图，然后判断每个点的度数是否为偶数。

代码：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int n,m,a[1001];
bool f[1001];
vector<int> g[1001];
void dfs(int u){
	f[u]=true;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!f[v])dfs(v);
	}
}
int main(){
	while(cin>>n){
		if(n==0)return 0;
		cin>>m;
		memset(a,0,sizeof(a));
		memset(f,false,sizeof(f));
		for(int i=1;i<=1000;i++)g[i].clear();
		int cnt=0;
		bool flag=true;
		for(int i=1;i<=m;i++){
			int u,v;
			cin>>u>>v;
			g[u].push_back(v);
			g[v].push_back(u);
			a[u]++,a[v]++;
		}
		dfs(1);
		for(int i=1;i<=n;i++){
			if(f[i]==false){
				flag=false;
			}
		}
		for(int i=1;i<=n;i++){
			if(a[i]%2==1||a[i]==0){
				flag=false;
				break;
			}
		}
		if(flag==false)cout<<"0\n";
		else cout<<"1\n";
	}
} 

B.构建欧拉图

思路

计算每个点的度数，若一个点的度数为奇数，那么sum++，最后输出sum/2,（因为一条边可以连两个点）。

代码

#include<iostream>
using namespace std;
int n,m,a[1000001],sum;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		a[u]++,a[v]++;
	}
	for(int i=1;i<=n;i++){
		if(a[i]&1==1){
			sum++;
		}
	}
	cout<<sum/2;
}

C.骑马修删栏

模板的变形

思路

用Hierholzer算法，求欧拉路径，不过破损围栏的范围并不知道，需要用l和r求出最小的编号和最大的编号。

代码

#include<iostream>
#include<stack>
using namespace std;
int m,g[501][501],l=5000,r,node[501],cnt=1;
stack<int> s;
void dfs(int u){
	for(int i=l;i<=r;i++){
		if(g[u][i]){
			g[u][i]--;
			g[i][u]--;
			dfs(i);
		}
	}
	s.push(u);
}
int main(){
	cin>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		l=min(min(l,u),v);
		r=max(max(r,u),v);
		g[u][v]++,g[v][u]++;
		node[u]++,node[v]++;
	}
	for(int i=l;i<=r;i++){
		if(node[i]&1==1){
			cnt=i;
			break;
		}
	}
	dfs(cnt);
	while(!s.empty()){
		cout<<s.top()<<"\n";
		s.pop();
	}
	return 0;
}

D.单词游戏

思路：

如果我们以盘子为节点建图，会发现这样程序很难跑。换个思路，我们可以以一个单词的首尾字母为节点，再进行建图，最后再dfs判断是否为欧拉图或半欧拉图。不过要注意的是，需要判断此图是否为连通图。另外，盘子是不能反转的，也就是说这个图本质上是一个有向图，不过为了方便判断是否为连通图，我们可以建一个无向图，再根据欧拉图的性质写出判断欧拉图的代码。

代码：

#include<iostream>
#include<cstring>
using namespace std;
int t,n,g[27][27],nodes[27],nodet[27],flag[27];
void dfs(int u){
	flag[u]=2;
	for(int i=1;i<=26;i++){
		if(flag[i]==1&&g[u][i]){
			flag[i]=2;
			dfs(i);
		}
	}
}
int main(){
	cin>>t;
	while(t--){
		memset(nodes,0,sizeof(nodes));
		memset(nodet,0,sizeof(nodet));
		memset(g,0,sizeof(g));
		memset(flag,-1,sizeof(flag));
		int k,a=0,b=0;
		bool f=true;
		cin>>n;
		for(int i=1;i<=n;i++){
			string z;
			cin>>z;
			int u=z[0]-'a'+1,v=z[z.size()-1]-'a'+1;
			g[u][v]++;
			g[v][u]++;
			nodes[u]++;//出度 
			nodet[v]++;//入度 
			k=u;
			flag[u]=flag[v]=1;
		}
		dfs(k);
		for(int i=1;i<=26;i++){
			int node=nodet[i]-nodes[i];
			if(node==1)a++;
			if(node==-1)b++;
			if(a>1||b>1||flag[i]==1){
				f=false;
				break;
			}
			if(node!=0&&node!=1&&node!=-1){
				f=false;
				break;
			}
			
		}
		if(!f)cout<<"The door cannot be opened.\n";
		else cout<<"Ordering is possible.\n";
	}
	return 0;
}

E.划水

思路

建最短的边，使得原图变成欧拉图。算出每个节点需要的入度和出度，与周围最近的点进行匹配，最后输出建的新边长度之和。

代码

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,sum,s[100001],node[100001];
vector<int> in,out;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>node[i];
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		s[u]--,s[v]++;//出度--入度++ 
	}
	for(int i=1;i<=n;i++){
		if(s[i]<0)for(int j=s[i];j<0;j++)in.push_back(node[i]);//需要入度
		if(s[i]>0)for(int j=1;j<=s[i];j++)out.push_back(node[i]); 
	} 
	sort(in.begin(),in.end());
	sort(out.begin(),out.end());
	for(int i=0;i<in.size();i++){
		sum+=abs(in[i]-out[i]);
	}
	cout<<sum;
}

F.原始生物

#include<iostream>
#include<vector>
using namespace std;
int n,m,in[1005],ou[1005],ans,l,r;
bool fla,vis[1005],exi[1005];
vector<int>g[1005];
void dfs(int u){
	vis[u]=1;
	if(in[u]!=ou[u])fla=0;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!vis[v])dfs(v);
	} 
} 
int main(){
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>l>>r;
		g[l].push_back(r);
		g[r].push_back(l);
		ou[l]++;in[r]++;
		exi[l]=exi[r]=1; 
		n=max(n,max(l,r));
	} 
	for(int i=1;i<=n;i++){ 
		if(!exi[i])continue;
		ans+=max(in[i],ou[i]);
		if(!vis[i]){
			fla=1; 
			dfs(i);
			if(fla)ans++;
		}
	}
	cout<<ans;
	return 0;
}

G. Ant Trip

#include <iostream>
#include <vector>
#include <cmath>
#include <stack>
#include <cstring>
using namespace std;
int n,m,v[100001],f;
vector<int> a[100001];
void dfs(int x){
	if(v[x])return;
	v[x]=1;
	for(int i=0;i<a[x].size();i++){
		if(!v[a[x][i]]){
			dfs(a[x][i]);
		}
	}
	if(a[x].size()%2!=0)f++;
}
int main(){
	while(cin>>n>>m){
		for(int i=1;i<=10000;i++)a[i].clear();
		memset(v,0,sizeof(v));
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y;
			a[x].push_back(y);
			a[y].push_back(x);
		}
		int s=0;
		for(int i=1;i<=n;i++){
			if(v[i]||a[i].size()==0)continue;
			f=0;
			dfs(i);
			if(f==0)s++;
			else s+=f/2;
		}
		cout<<s<<endl;
	}
	return 0;
}