1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5  6 int n, q; 7 int a[1010][1010];  8 int vis[1010]; 9 int degree[1010];10 void dfs(int cur)11 {12     vis[cur] = 1;//如果能过去，就说明连通，标记为已经走过 13     for(int i = 1; i <= n; i++)14     {15         if(vis[i] == 0 && a[cur][i])16         {17             dfs(i);18         }19     }20 }21 int main()22 {23     int N;24     scanf("%d", &N);25     while(N--)26     {27         28         bool flag = true;29         scanf("%d %d", &n, &q);30         memset(a, 0, sizeof(a));31         memset(vis, 0, sizeof(vis));32         memset(degree, 0, sizeof(degree));33         int t1, t2;34         for(int i = 1; i <= q; i++)35         {36             scanf("%d %d", &t1, &t2);37             a[t1][t2] = 1;38             a[t2][t1] = 1;39             ++degree[t1];//统计节点的度数 40             ++degree[t2];41         }42         dfs(1);43         for(int i = 1; i <= n; i++)44         {45             if(vis[i] == 0)//如果图不连通 46             {47                 flag = false;48                 break;49             }   50         }51         int cnt = 0;52         if(flag)53         {54             for(int i = 1; i <= n; i++)55             {56                 if(degree[i] % 2 == 1)57                     cnt++;//统计奇度顶点的个数 58             }59             if(cnt != 0 &&  cnt != 2)60                 flag = false;61         }62         if(flag)63             printf("Yes\n");64         else65             printf("No\n");66         67         68     }69     return 0;70 }71         

 1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4  5 const int N = 1010; 6 int father[N], rank[N]; 7 int degree[N]; 8   9 int find(int n)10 {11     if (n != father[n])12         father[n] = find(father[n]);//路径压缩 13     return father[n];14 }15 //合并函数 16 void unin(int x, int y)17 {18     int n = find(x);19     int m = find(y);20     if(n != m)21     {22         //rank用来保存当前点有多少个孩子了，始终孩子少的归顺孩子多的，合并根节点 23         if (rank[n] > rank[m])24         {25             father[m] = n;26             rank[n]++;27         }28         else29         {30             father[n] = m;31             rank[m]++;32         }33         34     } 35 }36 int main()37 {38     int N;39     scanf("%d", &N);40     while(N--)41     {42         int p, q;43         scanf("%d %d", &p, &q);44         for(int i = 1; i <= p; i++)45             father[i] = i;//初始化每个节点的父亲为他本身 46         memset(rank, 0, sizeof(rank));//清零 47         memset(degree, 0, sizeof(degree));//统计每个节点的度， 48         int a, b;49         for(int i = 0; i < q; i++)50         {51             scanf("%d %d", &a, &b);52             unin(a, b);53             ++degree[a];54             ++degree[b];55         }56         bool flag = true;57         int t = father[1];//判断是否连通分量是否为1 58         for(int i = 2; i <= p; i++)59         {60             if (t != father[i])61             {62                 flag = false;63                 break;64             }65         }66         67         if(flag)68         {69             int cnt = 0;70             for(int i = 1; i <= q; i++)71             {72                 if(degree[i] % 2 == 1)//统计奇度定点的个数 73                     cnt++; 74             }75             if(cnt != 0 && cnt != 2)76             flag = false;77         }78         if(flag)79             printf("Yes\n");80         else81             printf("No\n");82     }83     return 0;84 }