本文共 1003 字,大约阅读时间需要 3 分钟。
题目描述
欧拉回路是指不令笔离开纸面,可画过图中每条边仅一次,且可以回到起点的一条回路。现给定一个图,问是否存在欧拉回路?
输入描述:
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是节点数N ( 1 < N < 1000 )和边数M;随后的M行对应M条边,每行给出一对正整数,分别是该条边直接连通的两个节点的编号(节点从1到N编号)。当N为0时输入结束。输出描述:
每个测试用例的输出占一行,若欧拉回路存在则输出1,否则输出0。示例1
输入
3 31 21 32 33 21 22 30输出
10
判断欧拉回路的充要条件:除孤立节点外,其它节点满足
1
.连通
2
.度为偶数
#include#include #define MAX 1001int root[MAX];int cnt[MAX];int find(int x){//查找某个结点所在树的根结点 if(root[x]!=-1) return find(root[x]);//若当前结点为非根结点,则一直查找其双亲结点 else return x;}int main(){ int N,M; while(scanf("%d",&N)!=EOF){ int i,x,y; if(N==0) break; scanf("%d",&M); for(i=1;i<=N;++i){ cnt[i]=0;//初始化度数 root[i]=-1;//初始化每个点的根结点 } for(i=0;i 0) vnum++;//统计所有节点中根结点的个数 if(cnt[i]%2!=0)//判断度是否为偶数 flag=1; } if(vnum>1 || flag) printf("0\n");//不是欧拉回路 else printf("1\n");//是欧拉回路 } return 0;}
转载地址:http://dpssi.baihongyu.com/