天梯赛L2-024 部落（并查集+标记）

墨蓝 2022-02-25 03:28 360阅读 0赞

**Problem Description:**

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

**Input:**

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

K P\[1\] P\[2\] ⋯ P\[K\]

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

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

**Output:**

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

**样例烦请大家在原题上查看。**

**思路：**

这题是一道较为简单的并查集题目。我认为第一个难点在于读取随后的N行的每一行时如何进行合并，可以**提前声明一个变量pre用来存储上一个元素的下标，轮到当前元素并入并查集的时候只需要与pre进行合并；**第二个难点在于统计社区的总人数，**因为一个人可以出现在不同的朋友圈中，即一个人在不同的行可以重复出现，**所以可以用**标记法**统计社区总人数。询问互不相交的部落的个数就是让你统计并查集的个数，还是用**标记法**进行统计。判断是否属于同一部落直接调用Find函数查询两人的根结点是不是同一个就可以了，属于并查集的基本操作，这里就不赘述了。

**上AC代码：**

#include <bits/stdc++.h>
    int f[10001];
    bool dp[10001];
    bool vis[10001];
    int Find(int x)
    {
        if(x==f[x])
            return x;
        else
            return f[x]=Find(f[x]);
    }
    int n,sum,q;
    int main()
    {
        int i,j;
        scanf("%d",&n);
        sum=0;
        //初始化f数组
        for(i=1;i<=10000;i++)
        {
            f[i]=i;
        }
    
        memset(vis,0,sizeof(vis));
        memset(dp,0,sizeof(dp));
    
        //临时变量
        int num;
        int temp;
        int pre;
        for(i=0;i<n;i++)
        {
            scanf("%d",&num);
            for(j=0;j<num;j++)
            {
                scanf("%d",&temp);
                if(j>0)
                {
                    f[Find(pre)]=Find(temp);
                }
                pre=temp;
                if(vis[temp]==false)
                {
                    sum++;
                }
                vis[temp]=true;
            }
        }
        int Count=0;
        for(i=1;i<=sum;i++)
        {
            if(dp[Find(i)]==false)
            {
                Count++;
            }
            dp[Find(i)]=true;
        }
        printf("%d %d\n",sum,Count);
    
        scanf("%d",&q);
        for(i=0;i<q;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(Find(a)==Find(b))
            {
                printf("Y\n");
            }
            else
            {
                printf("N\n");
            }
        }
    
        return 0;
    }