NYOJ-42 一笔画问题

这个题可以有两种方式来解决，一个是搜索来解决，另一个是用并查集，后者较前者来说要更快点

整个题的思路就是先判断整个图是否连通，然后再判断是否为欧拉图，即图中奇度顶点的个数是否为0或者2，如果是0或者2的话就是欧拉图，就可以一笔画，所以，用搜索是来判断这个图是否连通，并查集也是，下面是代码的实现：

方法一(搜索):

 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
");
64         else
65             printf("No
");
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         else
29         {
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
");
80         else
81             printf("No
");
82     }
83     return 0;
84 }