哥尼斯堡的“七桥问题”(25分）（欧拉回路，并查集）

哥尼斯堡的“七桥问题”（25 分）

哥尼斯堡是位于普累格河上的一座城市，它包含两个岛屿及连接它们的七座桥，如下图所示。

可否走过这样的七座桥，而且每桥只走过一次？瑞士数学家欧拉(Leonhard Euler，1707—1783)最终解决了这个问题，并由此创立了拓扑学。

这个问题如今可以描述为判断欧拉回路是否存在的问题。欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个无向图，问是否存在欧拉回路？

输入格式:

输入第一行给出两个正整数，分别是节点数N (1≤N≤1000)和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。

输出格式:

若欧拉回路存在则输出1，否则输出0。

输入样例1:

6 10
1 2
2 3
3 1
4 5
5 6
6 4
1 4
1 6
3 4
3 6

输出样例1:

1

输入样例2:

5 8
1 2
1 3
2 3
2 4
2 5
5 3
5 4
3 4

输出样例2:

0
 1 /* 
 2 5-32 哥尼斯堡的“七桥问题”  (25分) 
 3 http://pta.patest.cn/pta/test/15/exam/4/question/859 
 4 并查集（用来判断是否连通） 和 一笔画(每个节点的度必须为偶数) 
 5 */  
 6 #include <cstdio>  
 7 #include <cstdlib>  
 8 #include <iostream>  
 9 #include <vector>  
10 #include <queue>  
11 #include <map>  
12 #include <algorithm>  
13 #include <set>  
14 #include <string>  
15   
16 using namespace std;  
17   
18 #define N 1005  
19   
20 int n , m ;  
21   
22 int degree[N] ;  
23 int fa[N] ;  
24   
25 int find(int x)  
26 {  
27     if(x == fa[x])  
28         return x ;  
29     return fa[x] = find(fa[x]);  
30 }  
31   
32 void merg(int x, int y)  
33 {  
34     fa[find(y)] = find(x) ;  
35 }  
36   
37 int main()  
38 {  
39     //freopen("in.txt","r",stdin);  
40     //freopen("out.txt","w",stdout);  
41     int i  , u , v;   
42     while( scanf("%d%d",&n,&m) != EOF)  
43     {  
44         for(i = 1 ; i<= n ; i++)  
45         {  
46             fa[i] = i ;  
47             degree[i] = 0 ;  
48         }  
49         for(i = 0 ; i< m ; i++)  
50         {  
51             scanf("%d%d",&u,&v);  
52             degree[u] ++;  
53             degree[v] ++;  
54             if(find(u) != find(v))  
55                 merg(u ,v);  
56         }  
57           
58         bool flag1 = true;  
59         for(i = 1 ;i <= n ; i++)  
60         {  
61             if(degree[i] % 2 != 0)  
62             {  
63                 flag1 = false ;  
64                 break;  
65             }  
66         }  
67         if(flag1)  
68         {  
69             set<int> faset ;  
70             for(i = 1 ;i <= n ; i++)  
71             {  
72                 faset.insert(find(i));  
73             }  
74             if((int)faset.size() == 1)  
75             {  
76                 printf("1
");  
77             }else{  
78                 printf("0
");  
79             }  
80         }else{  
81             printf("0
");  
82         }  
83     }  
84     return 0 ;  
85 }
  1. /* 
  2. 5-32 哥尼斯堡的“七桥问题”  (25分) 
  3. http://pta.patest.cn/pta/test/15/exam/4/question/859 
  4. 并查集（用来判断是否连通） 和 一笔画(每个节点的度必须为偶数) 
  5. */  
  6. #include <cstdio>  
  7. #include <cstdlib>  
  8. #include <iostream>  
  9. #include <vector>  
  10. #include <queue>  
  11. #include <map>  
  12. #include <algorithm>  
  13. #include <set>  
  14. #include <string>  
  15.   
  16. using namespace std;  
  17.   
  18. #define N 1005  
  19.   
  20. int n , m ;  
  21.   
  22. int degree[N] ;  
  23. int fa[N] ;  
  24.   
  25. int find(int x)  
  26. {  
  27.     if(x == fa[x])  
  28.         return x ;  
  29.     return fa[x] = find(fa[x]);  
  30. }  
  31.   
  32. void merg(int x, int y)  
  33. {  
  34.     fa[find(y)] = find(x) ;  
  35. }  
  36.   
  37. int main()  
  38. {  
  39.     //freopen("in.txt","r",stdin);  
  40.     //freopen("out.txt","w",stdout);  
  41.     int i  , u , v;   
  42.     while( scanf("%d%d",&n,&m) != EOF)  
  43.     {  
  44.         for(i = 1 ; i<= n ; i++)  
  45.         {  
  46.             fa[i] = i ;  
  47.             degree[i] = 0 ;  
  48.         }  
  49.         for(i = 0 ; i< m ; i++)  
  50.         {  
  51.             scanf("%d%d",&u,&v);  
  52.             degree[u] ++;  
  53.             degree[v] ++;  
  54.             if(find(u) != find(v))  
  55.                 merg(u ,v);  
  56.         }  
  57.           
  58.         bool flag1 = true;  
  59.         for(i = 1 ;i <= n ; i++)  
  60.         {  
  61.             if(degree[i] % 2 != 0)  
  62.             {  
  63.                 flag1 = false ;  
  64.                 break;  
  65.             }  
  66.         }  
  67.         if(flag1)  
  68.         {  
  69.             set<int> faset ;  
  70.             for(i = 1 ;i <= n ; i++)  
  71.             {  
  72.                 faset.insert(find(i));  
  73.             }  
  74.             if((int)faset.size() == 1)  
  75.             {  
  76.                 printf("1 ");  
  77.             }else{  
  78.                 printf("0 ");  
  79.             }  
  80.         }else{  
  81.             printf("0 ");  
  82.         }  
  83.     }  
  84.     return 0 ;  
  85. }  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/caiyishuai/p/13271146.html