并查集初步题目（1）

时间：2015-11-13 18:19:30 阅读：317 评论：0 收藏：0 [点我收藏+]

多个元素，分别属于不同的集合。要反复查找其中的特定的元素时，速度可能较慢。因此所采用的一种算法。

并查集时间复杂度为O(n).

主要用于：

1.判断图的连通性（最小生成树）

2.判断联通块

A题：

Description

上次Gardon的迷宫城堡小希玩了很久，现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。
技术分享

Input

输入包含多组数据，每组数据是一个以0 0结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为1，且不超过100000。每两组数据之间有一个空行。
整个文件以两个-1结尾。

Output

对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路，那么输出"Yes"，否则输出"No"。

Sample Input

6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1

Sample Output

Yes Yes No

代码：

 1 #include <iostream>
 2 #include <stdlib.h>
 3 #include <stdio.h>
 4 #include <string.h>
 5 
 6 #define MAX 100010
 7 
 8 using namespace std;
 9 int fa[MAX];
10 int vis[MAX];
11 
12 
13 int find(int x)
14 {
15     return x == fa[x] ? x : fa[x] = find(fa[x]) ;
16 }
17 
18 int main()
19 {
20     int a , b;
21     memset(fa,-1,MAX * sizeof(int));
22     memset(vis,0,MAX * sizeof(int));
23     int flag = 1;
24     while(1)
25     {
26         scanf("%d%d",&a,&b);
27         if (a < 0 && b < 0)
28         {
29             break;
30         }
31         if (a == 0 && b == 0)
32         {
33             if (flag == 0) cout << "No" <<endl;
34             else 
35             {
36                 int key = 0;
37                 int temp = -1;
38                 for (int i = 0; i < MAX; ++i)
39                 {
40                     if (vis[i])
41                     {
42                         if(temp < 0) temp = find(i);
43                         else if (temp != find(i)) { key = 1 ; break;}
44                     }
45                 }
46                 if(key) cout << "No" <<endl;
47                 else cout << "Yes" <<endl;
48 
49             }
50             
51             memset(fa,-1,MAX * sizeof(int));
52             memset(vis,0,MAX * sizeof(int));
53             flag = 1;
54             continue;
55 
56         }
57         
58         if (fa[a] < 0)
59         {
60             vis[a] = 1;
61             fa[a] = a;
62         }
63         if (fa[b] < 0 )
64         {
65             vis[b] = 1;
66             fa[b] = b;
67         }
68         
69         if (find(a) != find(b))
70         {
71             find(a) < find(b) ? fa[find(b)] = find(a) : fa[find(a)] = find(b);
72         }
73         else if(find(a) == find(b)) flag = 0;
74 
75         
76 
77 
78     }
79     return 0;
80 
81 }

坑点：题目中要求只有一个联通，如果没有将所有的点全部连起来，也是NO。

B题：

Description

Today is Ignatius‘ birthday. He invites a lot of friends. Now it‘s dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.

One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.

For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.

Input

The input starts with an integer T(1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.

Output

For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.

Sample Input

2 5 3 1 2 2 3 4 5 5 1 2 5

Sample Output

2 4

思路很简单，初始时所有的人都是单独的，所以table ＝ N

然后每进行一次合并操作，table－－；

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <string.h>
 5 #define MAX 1010
 6 int fa[MAX];
 7 using namespace std;
 8 
 9 int find(int x) 
10 {
11     return x == fa[x] ? x : fa[x] = find(fa[x]);
12 }
13 
14 
15 
16 int main()
17 {
18     int n;
19     while(~scanf("%d",&n))
20     {
21         for(int i = 0 ; i < n ; i++)
22         {
23             int tablenum = 0;
24              int num;
25              int cases;
26              scanf("%d%d",&num,&cases);
27              for(int j = 1; j <= num ; j++) 
28              {
29                  fa[j] = j;
30              }
31              tablenum = num;
32              
33              for (int k = 0; k < cases; ++k)
34              {
35                  int a , b;
36                  scanf("%d%d",&a,&b);
37                  if (find(a) != find(b))    
38                  {
39                      find(a) < find(b) ? fa[find(b)] = find(a) : fa[find(a)] = find(b);
40                      tablenum--;
41                  }
42 
43              }
44 
45 
46              cout << tablenum <<endl;
47 
48 
49         }
50     }
51     return 0;
52 }

C题：

Description

严重急性呼吸系统综合症( SARS), 一种原因不明的非典型性肺炎,从2003年3月中旬开始被认为是全球威胁。为了减少传播给别人的机会, 最好的策略是隔离可能的患者。

在Not-Spreading-Your-Sickness大学( NSYSU), 有许多学生团体。同一组的学生经常彼此相通,一个学生可以同时加入几个小组。为了防止非典的传播,NSYSU收集了所有学生团体的成员名单。他们的标准操作程序(SOP)如下：

一旦一组中有一个可能的患者, 组内的所有成员就都是可能的患者。

然而,他们发现当一个学生被确认为可能的患者后不容易识别所有可能的患者。你的工作是编写一个程序, 发现所有可能的患者。

Input

输入文件包含多组数据。

对于每组测试数据：

第一行为两个整数n和m, 其中n是学生的数量, m是团体的数量。0 < n <= 30000，0 <= m <= 500。

每个学生编号是一个0到n-1之间的整数，一开始只有0号学生被视为可能的患者。

紧随其后的是团体的成员列表，每组一行。

每一行有一个整数k，代表成员数量。之后,有k个整数代表这个群体的学生。一行中的所有整数由至少一个空格隔开。

n = m = 0表示输入结束，不需要处理。

Output

对于每组测试数据, 输出一行可能的患者。

Sample Input

100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0

Sample Output

4
1
1

　由于初始的感染者已经被确定。所以我们每次都以小标号的人为大标号的人为father，最后只要遍历一遍所有人。find(a) == 0 就能确定a为患者。

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 #define MAX 30010
 5 
 6 int fa[MAX];
 7 
 8 using namespace std ;
 9 
10 int find(int x) 
11 {
12     return x == fa[x] ? x : fa[x] = find(fa[x]);
13 }
14 
15 
16 int main()
17 {
18     int N,M;
19     while(1)
20     {
21         scanf("%d%d",&N,&M);
22         if(!N && !M) break;
23         for(int m = 0 ; m < N ; m++) fa[m] = m;
24         int ans = 0;
25         for (int i = 0; i < M; ++i)
26         {
27             int n;
28             scanf("%d",&n);
29             ////////
30             int a ;
31             int b ;
32             scanf("%d",&a);
33             for (int k = 1; k < n; ++k)
34             {
35                 scanf("%d",&b);
36                 if (find(a) != find(b))
37                 {
38                     find(a) < find(b) ? fa[find(b)] = find(a) : fa[find(a)] = find(b);
39                 }
40                 a = b;
41                 
42             }
43 
44         }
45         for(int m = 0 ; m < N ; m++)
46         {
47             if (find(m) == 0)
48             {
49                 ans++;
50             }
51         }
52         cout << ans <<endl;
53     }
54     return 0;
55 }

并查集初步题目（1）

原文：http://www.cnblogs.com/ticsmtc/p/4962629.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)