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

一道典型的查并集的题目,如果你还不了解查并集,可以参考一下这篇文章:查并集基础

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

总人数好办,因为题目说了人的编号从 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;
} 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • L3-004. 肿瘤诊断

    在诊断肿瘤疾病时,计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域,请你计算肿瘤的体积。

    指点
  • 51Nod--1018 排序

    题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1018

    指点
  • 查找算法

    查找,作为应用最为广泛和最基础的算法思想之一,几乎在所有应用程序之中都有它的思想身影。往细一点说:查找可以有 顺序查找、二分查找、散列表查找,下面依次来看一下这...

    指点
  • Leetcode Golang 1. Two Sum.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88866806

    anakinsun
  • P2658 汽车拉力比赛

    题目描述 博艾市将要举行一场汽车拉力比赛。 赛场凹凸不平,所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500),每个单元格的海拔范围在0到10^9之...

    attack
  • 1545 最简单排序

    个人博客:double.win 1545 最简单排序  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

    attack
  • vs---错误收集并自己解决后归纳

    1。C++编译时,出现这样的错误 d:\program files\microsoft visual studio\vc98\include\stdio.h(3...

    Gxjun
  • 挑战程序竞赛系列(82):4.3 LCA(2)

    挑战程序竞赛系列(82):4.3 LCA(2) 传送门:POJ 1986: Distance Queries 题意: LCA距离:快速查询树中任意两个节点间...

    用户1147447
  • 快速排序

    快速排序思想:如果要排数组p到r之间的一组数据,选择p到r之间任意一个一个数据作为pivot(分区点,这里选择的是s[r]作为pivot)。遍历p到r之间的数据...

    用户2937493
  • 数组的简单练习题

    1.将一个给定的整型数组转置输出, 例如: 源数组,1 2 3 4 5 6 转置之后的数组,6 5 4 3 2 1

    阮键

扫码关注云+社区

领取腾讯云代金券