1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 #include<iostream> 5 using namespace std; 6 int fa[20005],a[105]; 7 int fin(int x)//查找两个结点是否出自同一个父亲节点 8 { 9     return fa[x]==x?fa[x]:fa[x]=fin(fa[x]);10 }11 int unin(int x,int y)//将有关联两个节点连结在一起12 {13     return fa[fin(y)]=fin(x);14 }15 int main()16 {17 18     int m,n;19     while(cin>>m>>n){20     memset(a,0,sizeof(a));21     memset(fa,0,sizeof(fa));22     for(int i=1;i<=m;i++){23         fa[i]=i;/初始化父亲节点24     }25     int x;int y;26     for(int i=1;i<=n;i++){27         cin>>x>>y;28         if(fin(x)!=fin(y)){//如果两个节点还没有出自同一个结点，那么29             unin(x,y);//吧这两个节点连结在一起30         }31         a[x]++;//同时记录结点的度数32         a[y]++;//同时记录结点的度数33     }34     int sum1=0;35     for(int i=1;i<=m;i++){36         if(a[i]%2!=0){37             sum1++;38         }39         40     }41     int flag=0;42     for(int i=1;i<=m;i++){43         if(fin(i)!=fin(1)){//如果结点并不是相连续的，那么44             flag=1;//记录flag的值45             break;//跳出46         }47     }48      if(flag==1)49         {50             printf("Graph is not connected!\n");51             continue;52         }53         if(sum1==2)54         {55             printf("have Euler path\n");56         }57         else if(sum1==0)58         {59             printf("have Euler Circuit\n");60         }61         else62         {63             printf("have no Euler path\n");64         }65 66     }67     return 0;68 }69  70 71 72  73  74