- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- // 这个题可以无视题目, 只需要注意 (如果无向图连通并且所有结点的度都是偶数, 则存在欧拉回路, 否则不存在. )
- int map[1000][1000],visited[1000],du[1000];
- int n,m,sum,i;
- void DFS(int t)
- {
- visited[t]=1;
- for(i=1; i<=n; i++)
- {
- if(visited[i]==0&&map[t][i]==1)
- {
- sum++;
- // 每走过一条路加一, 在下方的判断中, 是判断的路的条数而不是点的个数 if(sum==n-1)
- DFS(i);
- }
- }
- }
- int main()
- {
- int T;
- scanf("%d",&T);
- while(T--)
- {
- sum=0;
- memset(map,0,sizeof(map));
- memset(du,0,sizeof(du));
- memset(visited,0,sizeof(visited));
- scanf("%d%d",&n,&m);
- while(m--)
- {
- int a,b;
- scanf("%d%d",&a,&b);
- map[a][b]=map[b][a]=1;
- du[a]++;
- du[b]++;
- }
- DFS(1);
- for(i=1; i<=n; i++)
- {
- if(du[i]%2!=0)
- {
- sum=0;
- break;
- }
- }
- if(sum==n-1)
- // 这里判断是否可以全部联通
- printf("1\n");
- else
- printf("0\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3269685.html