[并查集]L2-024. 部落

L2-024. 部落

时间限制

120 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

在一个社区里,每个人都有自己的小圈子,还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里,于是要请你统计一下,在一个给定社区中,到底有多少个互不相交的部落?并且检查任意两个人是否属于同一个部落。

输入格式:

输入在第一行给出一个正整数N(<= 104),是已知小圈子的个数。随后N行,每行按下列格式给出一个小圈子里的人:

K P[1] P[2] … P[K]

其中K是小圈子里的人数,P[i](i=1, .., K)是小圈子里每个人的编号。这里所有人的编号从1开始连续编号,最大编号不会超过104。

之后一行给出一个非负整数Q(<= 104),是查询次数。随后Q行,每行给出一对被查询的人的编号。

输出格式:

首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询,如果他们属于同一个部落,则在一行中输出“Y”,否则输出“N”。

输入样例:

1
2
3
4
5
6
7
8
4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7

输出样例:

1
2
3
10 2
Y
N

分析:

本题又是一道并查集。我的做法是用映射,将所有人映射到对应的圈子中。例如第i个圈子共有k个人,分别为k1…kj…kk。则map[kj]=i。倘若kj已经有对应的圈子,那将两个圈子联系起来。即Union(map[kj],i)。此外设置计数器sum,每一次执行完map[kj]=i之后sum++,即未重复的人加一。最后计算每一个圈子i是否等于pre[i],计算独立圈子的个数。判断两个人是否是一个部落,只需查询他们映射的圈子是否相同,即root(map[a])是否等于root(map[b])。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>  
#include<cstdio>
#define MAXN 10005
using namespace std;
int N, k;
int pre[MAXN];
int maps[MAXN];
int root(int x) {
while (x != pre[x]) {
pre[x] = pre[pre[x]];
x = pre[x];
}
return x;
}
void Union(int px,int py) {
px = root(px);
py = root(py);
if (px != py)
pre[py] = px;
}
int main() {
cin >> N;
int sum = 0;
for (int i = 0; i < MAXN; i++) {
pre[i] = i;
maps[i] = 0;
}
for (int i = 1; i <= N; i++) {
cin >> k;
while (k--) {
int temp;
cin >> temp;
if (!maps[temp]) {
maps[temp] = i;
sum++;
}
else
Union(maps[temp], i);
}
}
int count = 0;
for (int i = 1; i <= N; i++)
if (pre[i] == i)
count++;
printf("%d %d\n", sum, count);
cin >> k;
while (k--) {
int xx, yy;
cin >> xx >> yy;
if (root(maps[xx]) == root(maps[yy]))
printf("Y\n");
else
printf("N\n");
}
return 0;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!