这个题可以有两种方式来解决， 一个是搜索来解决，另一个是用并查集，后者较前者来说要更快点
整个题的思路就是先判断整个图是否连通，然后再判断是否为欧拉图，即图中奇度顶点的个数是否为0或者2， 如果是0或者2的话就是欧拉图，就可以一笔画，所以，用搜索是来判断这个图是否连通，并查集也是，下面是代码的实现：
方法一(搜索):
1 #include2 #include 3 #include 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 #include2 #include 3 #include 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 }