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

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])。

#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;  
}