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