【算法每日一练]-图论（保姆级教程篇13 欧拉路径，回路）

目录

?判断有向图有欧拉回路

?判断有向图有欧拉路径

????????

如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)。

（每个点都经过一次就是旅行商问题）

预备知识：

有向图有欧拉路径：

等价于：非0度节点连通，且所有节点入度等于出度(欧拉回路) 或 有n-2个节点入度等于出度，另外两个节点一个多1一个少1

????????
无向图有欧拉路径： ?

等价于：连通图，且没有度为奇数的节点(欧拉回路) 或 只有两个2个度为奇数的节点?

????????

????????????????

?判断有向图有欧拉回路

判断连通使用并查集(一个for即可) 入度等于出度(一个for即可)

#include <bits/stdc++.h>       
using namespace std;
const int N=1e5+7;
int fa[N],in[N],out[N],n,m;
int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];//返回祖先 
}
void unity(int x, int y)
{
    int f1=find(x);//如果x和y本来就在同一个集合完全 不影响
    int f2=find(y);
    fa[f1]=f2;//合并树根 
}
bool check(){
	int pre;
	for(int i=1;i<=n;i++){
		int du=in[i]+out[i];
		if(!du)continue;//度为0直接跳过
		if(i!=1&&find(i)!=find(pre))return 0;//前面的点是否和当前点在同一个集合
		pre=i;
	}
	return 1;
}
int main()
{
		cin>>n>>m;int x,y;
	    for(int i=1; i<=n; i++) fa[i]=i;
	    for(int i=1; i<=m; i++){
	    	scanf("%d %d", &x, &y);
	        in[y]++;out[x]++;
	        unity(x,y);//建树
		}
		if(!check()){//先判断非0度节点是否连通
			cout<<"No";return 0;
		}
		int f=0;
		for(int i=1;i<=n;i++){//再判断入度是否等于出度
			if(in[i]!=out[i]){f=1;break;}
		}
		if(f==1)cout<<"No";
		else cout<<"Yes";
}

参考样例
3 4
1 2
2 3
3 1
1 1
yes
4 8
1 2
1 3
1 4
2 3
2 3
3 2
3 4
4 3

No
?

????????
?判断有向图有欧拉路径

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int fa[N],in[N],out[N],n,m;
int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];//返回祖先 
}
void unity(int x, int y)
{
    int f1=find(x);//如果x和y本来就在同一个集合完全 不影响
    int f2=find(y);
    fa[f1]=f2;//合并树根 
}
bool check(){
	int pre;
	for(int i=1;i<=n;i++){
		int du=in[i]+out[i];
		if(!du)continue;//度为0直接跳过
		if(i!=1&&find(i)!=find(pre))return 0;//前面的点是否和当前点在同一个集合
		pre=i;
	}
	return 1;
}
int main()
{
		cin>>n>>m;int x,y;
	    for(int i=1; i<=n; i++) fa[i]=i;
	    for(int i=1; i<=m; i++){
	    	scanf("%d %d", &x, &y);
	        in[y]++;out[x]++;
	        unity(x,y);//建树
		}
		if(!check()){//先判断非0度节点是否连通
			cout<<"No";return 0;
		}
		int f1=0,f2=0,f3=0;
		for(int i=1;i<=n;i++){
			if(in[i]==out[i])f1++;
			else if(in[i]-out[i]==1)f2++;
			else if(out[i]-in[i]==1)f3++;
		}
		if((f1==n)||(f1==n-2&&f2==1&&f3==1))cout<<"Yes";
		else cout<<"No";
}

参考样例
4 3?
1 2
2 3
3 4
YES
4 8
1 2
1 3
1 4
2 3
2 3
3 2
3 4
4 3

No
?