3364=数据结构实验之图论八：欧拉回路

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 //这个题可以无视题目，只需要注意（如果无向图连通并且所有结点的度都是偶数，则存在欧拉回路，否则不存在。 ）
 5 int map[1000][1000],visited[1000],du[1000];
 6 int n,m,sum,i;
 7 void DFS(int t)
 8 {
 9     visited[t]=1;
10     for(i=1; i<=n; i++)
11     {
12         if(visited[i]==0&&map[t][i]==1)
13         {
14             sum++;
15 //每走过一条路加一，在下方的判断中，是判断的路的条数而不是点的个数if(sum==n-1)
16             DFS(i);
17         }
18     }
19 }
20 int main()
21 {
22     int T;
23     scanf("%d",&T);
24     while(T--)
25     {
26         sum=0;
27         memset(map,0,sizeof(map));
28         memset(du,0,sizeof(du));
29         memset(visited,0,sizeof(visited));
30         scanf("%d%d",&n,&m);
31         while(m--)
32         {
33             int a,b;
34             scanf("%d%d",&a,&b);
35             map[a][b]=map[b][a]=1;
36             du[a]++;
37             du[b]++;
38         }
39         DFS(1);
40         for(i=1; i<=n; i++)
41         {
42             if(du[i]%2!=0)
43             {
44                 sum=0;
45                 break;
46             }
47         }
48         if(sum==n-1)
49 //            这里判断是否可以全部联通
50             printf("1
");
51         else
52             printf("0
");
53     }
54     return 0;
55 }