欧拉回路

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 10643    Accepted Submission(s): 3881

Problem Description

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

 

 

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

 

 

代码：超级水题（2015.8.13）

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 using namespace std; 6 #define Max 1010 7 char Str[Max]; 8 int EDG_Count;/*统计边数*/ 9 int ID[Max];/*并查集判断是否为同一幅图*/10 //int InD[M];/*入度*/11 //int OuD[M];/*出度*/12 int DuD[Max];13 int Find(int x)14 {15     if(x!=ID[x])ID[x]=Find(ID[x]);16     return ID[x];17 }18 void Cread(int N)19 {20     for(int i=0;i<=N;i++)21     {22         ID[i]=i;DuD[i]=0;23     }EDG_Count=0;24 }25 void Add(int a,int b)26 {27     int A=Find(a);28     int B=Find(b);29     if(A!=B){ID[A]=B;EDG_Count++;}30 }31 32 void Update(int a,int b)33 {34     Add(a,b);35     DuD[a]++;DuD[b]++;36     //OuD[a]++;InD[b]++;37 }38 39 int main()40 {41     int T,N,M,i,a,b,sign1,sign2,sign3;42     while(scanf("%d",&N)&&N)43     {44         Cread(N);45         scanf("%d",&M);46         for(i=1;i<=M;i++)47         {48             scanf("%d%d",&a,&b);49             Update(a,b);50         }51         sign1=sign2=0;52         for(i=1;i<=N;i++)53         {54             if(DuD[i]%2==0)sign2++;55             else sign1++;56         }57         if(EDG_Count!=N-1)/*是否构成一幅图*/58             {printf("0\n");continue;}59         if(sign1==2&&sign2==N-2)/*链的情况,题目要求*/60             printf("0\n");61         else if(sign1==0&&sign2==N) /*环的情况*/62             printf("1\n");63         else64             printf("0\n");65     }66     return 0;67 }