欧拉路径 & 欧拉回路

定义 & 判断

欧拉路径定义：图中经过所有边恰好一次的路径叫欧拉路径，如果此路径的起点和终点相同，则称其为一条欧拉回路。
欧拉路径 & 回路判断：
- 有向图欧拉路径：图中恰好存在 $1$ 个点出度比入度多 $1$ （即为起点）， $1$ 个点入度比出度多 $1$ （即为终点），其余点的入度等于出度。
- 有向图欧拉回路：所有点的入度和出度都一样。（起点和终点任选）
- 无向图欧拉路径：图中恰好存在 $2$ 个点的度数是奇数（就是欧拉路径的起点和终点），其余点为偶数。
- 无向图欧拉回路：所有点的度数都是偶数。（起点和终点任选）
至于证明，欧拉图 Oi-Wiki 上有证明，有兴趣者或想要更深入了解的读者可以看看。

易错点 & 声明

你选的起点和终点不能是孤立点，因为这样会炸掉。
不管是欧拉路径还是欧拉回路，都需要满足一个条件：除了孤立点之外，将有向图改成无向图，该图连通。
无向图欧拉路径的起点和终点就是那两个度数是奇数的点中任意排列就行。（没有先后）

例题 1 && 欧拉路径 & 回路判断好题

题目链接：LOJ 10106。

这一道题有数不胜数的坑，读者可以通过注释来了解坑点。

大体思路：将一个字符串看成一条边，从左到右连接了两个字母。

代码：

CPP

#include<bits/stdc++.h>
#define x0 x_0
#define x1 x_1
#define y0 y_0
#define y1 y_1
#define yn y_n
#define j0 j_0
#define j1 j_1
#define jn j_n
#define k0 k_0
#define k1 k_1
#define d0 d_0
#define d1 d_1
#define LL long long
#define LD long double
#define Big __int128
#define STR string
#define US unsigned
#define ZPB push_back
#define ZPF push_front
#define PPB pop_back
#define PPF pop_front
#define next NXTNXT
using namespace std;
STR s; 
int t,n,fa[26],rdu[26],cdu[26]; // rdu[i]: 第 i 个点的入度；cdu[i]: 第 i 个点的出度
int find(int x) {return (fa[x]==x ? x : fa[x]=find(fa[x]));}
void Init(){
	memset(rdu,0,sizeof(rdu)),
	memset(cdu,0,sizeof(cdu));
	for(int i=0;i<26;++i) fa[i]=i;
	return ;
}
void merge(int x,int y){
	x=find(x),y=find(y);
	if(x==y) return ;
	fa[x]=y;
	return ;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		Init(),cin>>n;
		for(int i=1;i<=n;++i){
			cin>>s;
			char frt=s[0],bck=s[(int)s.size()-1];
			++cdu[frt-'a'],++rdu[bck-'a'],merge(frt-'a',bck-'a'); // 为什么是开头加出度，结尾加入度呢？结尾就是下一个字符串的开头，我们可以认为是进入了这个节点；开头是前一个字符串的结尾，我们可以认为是出去了这个节点。
		}
		bool fla=1;
		int chk=0,st=-1,ed=-1;
		while(!rdu[chk] && !cdu[chk]) ++chk; // 坑点 1: 不能选到孤立点，要找到一个不是孤立点的 i
		chk=find(chk);
		for(int i=0;i<26;++i){ 
			if((rdu[i] || cdu[i]) && (find(i)^chk)) {fla=0;break;} // 坑点 2: 判断连通性时需要排除孤点
			if(rdu[i]==cdu[i]) continue;
			if(rdu[i]+1==cdu[i]){
				if(~st) {fla=0;break;}
				st=i;
				continue;
			}
			if(rdu[i]==cdu[i]+1){
				if(~ed) {fla=0;break;}
				ed=i;
				continue;
			}
			fla=0; // 坑点 3: 如果 rdu[i],cdu[i] 不是上面的三种情况，则一定不合法
			break;
		}
		if(fla && (st==-1 && ed==-1 || (~st) && (~ed))) cout<<"Ordering is possible.\n"; // 坑点 4: 要么就是欧拉回路，要么就是欧拉路径且 st,ed 均存在，不能一个存在一个不存在，这样一定不行。
		else cout<<"The door cannot be opened.\n";
	}
	return 0;
}

欧拉路径 & 欧拉回路

文章操作

定义 & 判断

易错点 & 声明

例题 1 && 欧拉路径 & 回路判断好题

相关推荐

评论

欧拉路径 & 欧拉回路