signed

QiShunwang

“诚信为本、客户至上”

HDU1878(判断一个无向图是否存在欧拉回路)

2021/5/14 22:04:17   来源:

1.欧拉回路:定义:经过图(有向图或无向图)中每条边一次且仅一次并且行遍图中每个顶点的回路( 闭合的欧拉路径,即一个环,保证每条边都通过且仅通过一次)
2.问题1:判断一个无向图是否有欧拉回路的充要条件:
(1)图G是连通的,无孤立的点
(2)无向图奇度点数为0

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxx=1005;
const int inf=0x3f3f3f3f;
int e[maxx][maxx];
int indegree[maxx];
int vis[maxx];
int outdegree[maxx];
int n,m;
int cnt;//记录访问的顶点数
int mark;//标记是否所有的顶点都是连通的
void init(){
	cnt=0;
	mark=0;
	memset(indegree,0,sizeof(indegree));
	memset(outdegree,0,sizeof(outdegree));
	memset(e,0,sizeof(e));
	memset(vis,0,sizeof(vis));
}
void dfs(int u){
	vis[u]=1;
	cnt++;
	if(cnt==n&&mark==0){
		mark=1;
		return ;
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0){
			if(e[u][i]==1){
				dfs(i);
			}
		}
	}
}
int main(){
	while(scanf("%d",&n)!=EOF){
		if(n==0)break;
		scanf("%d",&m);
		init();
		for(int i=1;i<=m;i++){
			int a,b;
			scanf("%d %d",&a,&b);
			e[a][b]=e[b][a]=1;
			indegree[a]++;
			indegree[b]++;
		}
		dfs(1);
		int flag=1;
		for(int i=1;i<=n;i++){
			if(indegree[i]%2!=0){
				flag=0;
				break;
			}
		}
		if(mark==1&&flag==1){
			cout<<"1"<<endl;
		}else{
			cout<<"0"<<endl;
		}
	}
	return 0;
}