脚本宝典收集整理的这篇文章主要介绍了欧拉图，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

定义

通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路。

通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路。

具有欧拉回路的无向图或有向图称为欧拉图。

具有欧拉通路但不具有欧拉回路的无向图或有向图称为半欧拉图。

有向图也可以有类似的定义。

非形式化地讲，欧拉图就是从任意一个点开始都可以一笔画完整个图，半欧拉图必须从某个点开始才能一笔画完整个图。

性质

欧拉图中所有顶点的度数都是偶数。

若 (G) 是欧拉图，则它为若干个环的并，且每条边被包含在奇数个环内。

判别法

对于无向图 (G) ,

(G) 是欧拉图的充要条件是 (G) 联通，所有点的度数为偶数 ;

(G) 是半欧拉图的充要条件是 (G) 联通，只可能有 (0/2) 个点的度数为奇数 .

对于有向图 (G) ,

(G) 是欧拉图的充要条件是 (G) 联通，所有点处于同一个强连通分块里面，每个点的入度和出度相同 .

(G) 是半欧拉图的充要条件是

• 将 (G) 中的所有边视为无向边，此时所有点处于同一个联通块中 .
• 最多存在一个顶点 (d^+(u)-d^-(u)=1)
• 最多存在一个顶点 (d^-(u)-d^+(u)=1)
• 其余所有点的出度等于入度

欧拉图的代码实现

版子题，uoj #117. 欧拉回路 .

因为欧拉图是很多个环的并 .

所以，对于每一个环，都可以轻松定下访问的方向 .

此时，考虑如何将两个环合并，首先，这两个环能合并，必须要有点同时处于这两个环上，此时，这两个环的遍历方案一定能被合并 .

dfs 的时候当前点 (u) 考虑直接找到一条没有被访问的边 ((u,v)) ，dfs 下去，肯定会在某个点再次访问到 (u) ，此时，回溯的路径一定构成一个欧拉回路 ( 一定是在 dfs 之后把 (u) 计入答案序列中 ) .

时间复杂度和空间复杂度都为 (O(n+m)) . 要加弧优化 . 不然会退化成 (O(nm)) .

#include<bits/stdc++.h>
using namespace std;
inline int rd(){
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	int res=0;
	while(ch>='0'&&ch<='9'){
		res=(res<<3)+(res<<1)+ch-'0';
		ch=getchar();
	}
	return res;
}
inline void pr(int res){
	if(res==0){
		putchar('0');
		return;
	}
	int a[10],len=0;
	while(res>0){
		a[len++]=res%10;
		res/=10;
	}
	for(int i=len-1;i>=0;i--)
		putchar(a[i]+'0');
}
int type;
int n,m;
vector<pair<int,int> >g[100010];
int iter[100010];
int deg[100010];
bool vis[200010];
int mark[100010];
stack<int>s;
namespace undirected{
	void dfs(int x){
		mark[x]++;
		for(int &i=iter[x];i<(int)g[x].size();i++){
			int to=g[x][i].first,id=g[x][i].second;
			if(vis[abs(id)])continue;
			vis[abs(id)]=true;
			dfs(to);
			s.push(id);
		}
	}
	void work(){
		n=rd();m=rd();
		for(int i=1;i<=m;i++){
			int u=rd()-1,v=rd()-1;
			deg[u]++;
			deg[v]++;
			mark[u]=mark[v]=1;
			g[u].push_back(make_pair(v,i));
			g[v].push_back(make_pair(u,-i));
		}
		for(int i=0;i<n;i++){
			if(deg[i]&1){
				puts("NO");
				return;
			}
		}
		for(int i=0;i<n;i++){
			if(mark[i]==1){
				dfs(i);
				break;
			}
		}
		for(int i=0;i<n;i++){
			if(mark[i]==1){
				puts("NO");
				return;
			}
		}
		puts("YES");
		while(!s.empty()){
			if(s.top()<0)putchar('-');
			pr(abs(s.top()));
			putchar(' ');
			s.pop();
		}
		putchar('n');
	}
}
namespace directed{
	void dfs(int x){
		mark[x]++;
		for(int &i=iter[x];i<(int)g[x].size();i++){
			int to=g[x][i].first,id=g[x][i].second;
			if(vis[id])continue;
			vis[id]=true;
			dfs(to);
			s.push(id);
		}
	}
	void work(){
		n=rd();m=rd();
		for(int i=1;i<=m;i++){
			int u=rd()-1,v=rd()-1;
			deg[u]++;
			deg[v]--;
			mark[u]=mark[v]=1;
			g[u].push_back(make_pair(v,i));
		}
		for(int i=0;i<n;i++){
			if(deg[i]!=0){
				puts("NO");
				return;
			}
		}
		for(int i=0;i<n;i++){
			if(mark[i]==1){
				dfs(i);
				break;
			}
		}
		for(int i=1;i<n;i++){
			if(mark[i]==1){
				puts("NO");
				return;
			}
		}
		puts("YES");
		while(!s.empty()){
			pr(s.top());
			putchar(' ');
			s.pop();
		}
		putchar('n');
	}
}
int main(){
	type=rd();
	if(type==1)undirected::work();
	else directed::work();
	return 0;
}
/*inline? ll or int? size? min max?*/

题目

1. cf1610f Mashtali: a Space Oddysey

这道题重点不在于欧拉回路，而是在于想到可以缩边，此时可以用欧拉回路来缩边 . 题解

脚本宝典总结

以上是脚本宝典为你收集整理的欧拉图全部内容，希望文章能够帮你解决欧拉图所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。