11.30 — 12.6 欧拉回路

题目:
欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路?

Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是节点数N ( 1 < N < 1000 )和边数M;随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个节点的编号(节点从1到N编号)。当N为0时输入结束。

Output
每个测试用例的输出占一行,若欧拉回路存在则输出1,否则输出0。

Sample Input

3 3
1 2
1 3
2 3
3 2
1 2
2 3
0

Sample Output

1
0

首先了解一下欧拉回路(顺带提一下欧拉通路):

  • 概念:
    欧拉回路: 通过图中每条边且只通过一次,并且经过每一顶点的回路。
    欧拉通路: 通过图中每条边且只通过一次,并且经过每一顶点的通路。
  • 无向图是否具有欧拉通路或回路的判定:
    欧拉通路:图连通;图中只有0个或2个度为奇数的节点
    欧拉回路:图连通;图中所有节点度均为偶数
  • 有向图是否具有欧拉通路或回路的判定:
    欧拉通路:图连通;除2个端点外其余节点入度=出度;1个端点入度比出度大1;一个端点入度比出度小1 或 所有节点入度等于出度
    欧拉回路:图连通;所有节点入度等于出度

那么看这道题,首先可以判断该题为无向图,那么无向图是否具有欧拉通路的判定标准是:图是否连通 以及 图中所有结点度均为偶数
那么就想,该如何应用这两个判定标准?
首先关于判断图是否连通,判断连通可以用很好用的 并查集 ,也就是把所有输入的边用join()函数联合后,当一个点的根节点与其他点的根节点不等,则不连通,则返回0;也就是把 flag 置0;
关于如何判断途中所有结点度为偶数,我们可以引一个数组: du[ ] 用来记录每个结点的度,下标为结点编号。初始化都为0,这样输入的时候直接 du[i]++ (本来我觉得会很难,但其实只要输入的时候输入进去++就可以,毕竟输入进去的是一条边嘛,可不就度+1了

好啦,现在看一下代码:

#include<stdio.h>
#include<string.h>
int pre[1050]={0};
int du[1050]={0};
int n,m;
int find(int x){
	int r=x;
	while(r!=pre[r])
	{
		r = pre[r];
	}
//	int i=x,j;		//可以不用路径压缩
//	while(pre[i]!=r){
//		j = pre[i];
//		pre[i] = r;
//		i=j;
//	}
	return r;
} 
void join(int x,int y){
	int f1 = find(x);
	int f2 = find(y);
	if(f1 != f2){
		pre[f2] = f1;
	}
}
int main(){
	while(scanf("%d%d",&n,&m),n){
		memset(du,0,sizeof(du)); //初始化为0
		for(int i=1;i<=n;i++){
			pre[i] = i;			//前驱数组初始化~
		}
		for(int j=1;j<=m;j++){
			int q,p;
			scanf("%d%d",&q,&p);
			du[q]++;du[p]++;		//算每个结点度的值
			join(q,p);
		}
		int temp = find(1);		//选个根,看其他结点的根跟这个一样不
		int flag = 1;		//先初始化1
		for(int i=1;i<=n;i++){
			if(find(i)!=find(1)){		//不连通!
				flag = 0;
				break;
			}
			if(du[i]%2 != 0){		//存在度不为2的结点!
				flag = 0;
				break;
			}
//			if(du[i] & 1) flag=0;		//这个是我学到的一个,与1相与,奇数为真偶数为假
//			if(find(i)!=temp) flag=0;
		}
		printf("%d\n",flag);
	}
	return 0;
}
上一篇:如何解决Linux删除文件但是磁盘空间大小并没有释放的问题?


下一篇:清理Mac