L2-024. 部落

古城微笑少年丶 2022-05-31 09:12 209阅读 0赞

## L2-024. 部落 ##

题目链接：[L2-024. 部落][L2-024.]

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

输入格式：

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

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

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

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

输出格式：

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

输入样例：  
4  
3 10 1 2  
2 3 4  
4 1 5 7 8  
3 9 6 4  
2  
10 5  
3 7  
输出样例：  
10 2  
Y  
N

一道典型的查并集的题目，如果你还不了解查并集，可以参考一下这篇文章：[查并集基础][Link 1]。

我们很容易想到**将多个含有至少一个相同的编号的人所在的小圈子合并成一个大圈子，即为部落。**

总人数好办，**因为题目说了人的编号从 1 开始而且是顺序不间断的，那么编号最大的人的编号值就是总人数。**

部落数呢？根据上面的思路，当所有的圈子都通过查并集合并完成之后，我们就可以统计出部落数。  
那么最后是判断两个编号的人是否属于同一个部落。看起来有点麻烦。**我们可以定义一个 int 类型的哈希数组，用来保存数组下标对应的编号所代表的人所属的圈子。因为到最后圈子都合并成部落了，那么我们再通过合并后的查并集来判断两个人所属的圈子是否属于同一个部落。**

最后是代码：

#include <iostream>
    #include <cstring>
    using namespace std;
    const int MAXN = 10010; 
    
    // 查并集部分，储存每个圈子的编号
    int root[MAXN];
    // 圈子所在查并集树的高度，用于提高查并集查找效率 
    int high[MAXN];
    // 储存下标对应的编号所代表的人属于第几个圈子的哈希数组，
    // 用于判断不同的圈子是否能合并和寻找某个人所在的部落 
    int peoRoot[MAXN];
    
    // 寻找下标为 x 的圈子的祖先 
    int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]);
    }
    
    // 合并第 x 和第 y 个圈子成为一个大圈子 
    int merge(int x, int y) {
        int fX = find(x);
        int fY = find(y);
        if (fX != fY) {
            if (high[fX] < high[fY]) {
                root[fX] = fY;
            } else {
                root[fY] = fX;
                if (high[fX] == high[fY]) {
                    high[fX]++;
                }
            }
        }
    }
    
    // 判断编号为 x 的人和编号为 y 的人是否在同一个部落 
    bool isSame(int x, int y) {
        if (x == y) {
            return true;
        }
        // 两个人所属的圈子编号 
        int xRoot = peoRoot[x];
        int yRoot = peoRoot[y];
        // 找到两个人所在圈子所属的部落编号 
        while (root[xRoot] != xRoot) {
            xRoot = root[xRoot];
        }
        while (root[yRoot] != yRoot) {
            yRoot = root[yRoot];
        }
        return xRoot == yRoot;
    }
    
    void init() {
        memset(peoRoot, -1, sizeof(int)*MAXN);
        for (int i = 0; i < MAXN; i++) {
            root[i] = i; // 初始时第 i 个圈子的初始祖先为 i  
        }
    }
    
    int main() {
        init();
        int n, m, num;
        int peopleSum = -1; 
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> m;
            // 输入每个小圈子 
            for (int j = 0; j < m; j++) {
                scanf("%d", &num);
                // 编号是连续的，所以总人数就是编号最大的  
                if (peopleSum < num) {
                    peopleSum = num;
                }
                // 如果这个编号的人在别的圈子出现过，那么合并这两个圈子 
                if (peoRoot[num] != -1) {
                    merge(peoRoot[num], i);
                } else {
                    peoRoot[num] = i; 
                } 
            }
        }
        // 总共 0~n-1：n 个圈子，合并完成之后，
        // root 数组中值等于下标值的圈子编号即为一个部落的祖先
        // 有多少个部落祖先就有多少个部落
        int tribeSum = 0;
        for (int i = 0; i < n; i++) {
            if (root[i] == i) {
                tribeSum++;
            }
        }
        cout << peopleSum << " " << tribeSum << endl;
        // 判断人是否在一个部落 
        cin >> m;
        int t1, t2; 
        for (int i = 0; i < m; i++) {
            cin >> t1 >> t2;
            if (isSame(t1, t2)) {
                cout << "Y" << endl;
            } else {
                cout << "N" << endl;
            }
        }
    
        return 0;
    }

[L2-024.]: https://www.patest.cn/contests/gplt/L2-024
[Link 1]: http://blog.csdn.net/hacker_zhidian/article/details/60965556