并查集学习笔记

发布于 2018-07-20  144 次阅读


并查集是对集合进行查找与合并的一种数据结构

例题

luogu P1551 亲戚
时空限制

1000ms / 128MB

题目背景

若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。
题目描述
规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。

输入格式:

第一行:三个整数n,m,p,(n<=5000,m<=5000,p<=5000),分别表示有n个人,m个亲戚关系,询问p对亲戚关系。
以下m行:每行两个数Mi,Mj,1<=Mi,Mj<=N,表示Mi和Mj具有亲戚关系。
接下来p行:每行两个数Pi,Pj,询问Pi和Pj是否具有亲戚关系。

输出格式:

P行,每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

输入输出样例
输入样例#1:

6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6

输出样例#1:

Yes
Yes
No

很容易想到建立一个图论模型,然后dfs,但是这样时间复杂度太高,并查集是可以处理这样的任务的。

定义

并查集是对集合进行查找与合并的一种数据结构,一般用树实现。
并查集的操作分为两种:合并与查询

实现

我们可以开一个数组a[n],其中a[i]表示第i个人的父节点是a[i],
一开始,我们把每个人的父节点设为他们自己,即初始化a[i] = i。这时,所有人都可以理解为一个单独的个体,现在,我们开始合并亲戚,组成“家族”。

过程

合并

我们合并1和2为亲戚,我们合并时选择让左边的数成为父节点,即a[2] = 1。

合并1和5为亲戚,1为父节点,即a[5] = 1。

合并3和4为亲戚,3为父节点,即a[4] = 3。

合并5和2为亲戚,2为父节点,但我们发现2有了父节点,我们就递归寻找2,5的祖先节点,发现是一个,不合并。

合并1和3为亲戚,1为父节点,即a[3] = 1。

查找

查找1和4,我们递归查找他们的祖先节点,同时将他们的每一个父节点和自己都直接连接他们的祖先节点(1本身就是祖先节点,所以直接返回他自己),以降低搜索复杂度(路径压缩),我们通过查找发现1,4的祖先节点是一个,输出“Yes”。

查找2和3,我们递归查找他们的祖先(因为之前我们之前路径压缩过,所以可以很容易地搜索到),发现是一个祖先,输出“Yes”。

查找5和6,我们递归查找他们的祖先,找5返回1,找6返回6,发现不是一个,输出“No”。

AC 代码

#include <cstdio>
int n, m, p, a[10001] = { 0 };  //a[i]表示i的祖先是a[i]

int find(int x)
{
    if (a[x] == x) return x;      //如果找到祖先,即a[x]=x(自己的祖先是自己),返回节点的值
    //int a[x]的祖先 = find (a[x]);
    //a[x] = a[x]的祖先;
    //return a[x]的祖先;
    return a[x] = find(a[x]);     //递归查找祖先并更改父节点们的祖先
}

void merge(int xi, int yi)      //合并xi,yi
{
    int xz = find(xi), yz = find(yi);    //找祖先
    if (xz != yz) a[yz] = xz;
}

int main()
{
    scanf("%d%d%d", &n, &m, &p);

    for (int i = 1; i <= n; i++) a[i] = i;    //初始化把每个人的父节点设为他们自己

    int xi, yi;

    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &xi, &yi);
        merge(xi, yi); //合并xi,yi
    }

    for (int i = 1; i <= p; i++)
    {
        scanf("%d%d", &xi, &yi);

        if (find(xi) == find(yi))   //如果xi的祖先节点=yi的祖先节点
            printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

题目练习

P3367 【模板】并查集

P1892 [BOI2003]团伙