Shadowlove
并查集

access_time
brush 730个字
whatshot 18 ℃
百度收录:百度已收录

1:简介

什么是并查集呢?从名字就可以看出来:并是合并,查是查找,集是集合。并查集是用来处理集合的合并以及查找集合元素的问题的。

具体点说,看这张图:

现在有A,B,C三个组织,每个组织箭头的末端都是该组织的boss。

有一天,C组织的11和12见到了,但是他们之前不熟。那么他们是敌是友呢?

11说:“我的上级是10!”

12说:“我的上级是8!”

11说:”emm兄弟等我再问问我的上级10“

10说:”我的上级是9,咱去问问9。”

9说:“我的上级是8!”

8说:“我的上级就是我自己!”

哦,于是他们知道了,他们的老大全都是8,他们是好兄弟。

于是,我们可以写出找上级的代码:

int f[1000]//f里面存储的是第i个元素的“老大”
int findl(int x)//防止冲突,把这个函数命名成findl
{
    if(f[x]==x)
        return x;
    else
        return findl(f[x])
}

这样的话就可以找到每个人的最高层boss了。

但是如果有一天,11遇到了9,俩人虽然都是8的小弟,却没见过。于是....他俩还会重复的去找自己的boss...这样显然效率是很低下的。

于是我们想出了一个解决方案:每次查询的时候顺便把自己的上级的boss也记录下来,于是变成了这样:

int f[1000]//f里面存储的是第i个元素的“老大”
int findl(int x)//防止冲突,把这个函数命名成findl
{
    if(f[x]==x)
        return x;
    else
        return f[x]=find(f[x]);
}

也就是说,当11查询自己的boss的时候,10,9的boss也会被更新成8,这样的话可以减少不必要的计算。

用一张图来表示的话,就是说大家全是8哥的小弟,咱哥几个别分上下级了,咱的工作全是主人的任务罢了。

然后,某一天,A和B两个组织打了一架,B的老大被打服了,于是他说:“别打了别打了,我加入A组织好吧,我的老大就是1!。”

于是.....5,6,7的老大全变成了1。虽然很不爽,但至少不用挨揍了。

void mergel(int a,int b)
{
    int c=findl(a);//c是a的boss
    int d=findl(b);//d是b的boss
    if(c!=d)//咱俩boss不一样
        f[c]=d;//c的boss变成了d,d是王中王!
}(当然这样以后6和7的boss还没有变过来,再find一次就好咯)

2:例题

洛谷p3367

题目描述

如题,现在有一个并查集,你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,M,表示共有 N个元素和 M个操作。

接下来 M 行,每行包含三个整数 Zi,Xi,Yi。

当 Zi=1时,将 Xi与 Yi 所在的集合合并。

当 Zi=2 时,输出 Xi 与 Yi 是否在同一集合内,是的输出 Y ;否则输出 N

输出格式

对于每一个 Zi=2 的操作,都有一行输出,每行包含一个大写字母,为 Y 或者 N

输入输出样例

输入 #1

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出 #1

N
Y
N
Y

说明/提示

对于 30%30% 的数据,N≤10,M ≤20 。

对于 70%70% 的数据,N ≤100,M ≤1e3 。

对于 100%100% 的数据,1≤N≤1e4,1≤M≤2×1e5 。

看完上面的应该没什么大问题了,直接上代码吧:

#include <bits/stdc++.h>
using namespace std;
int f[10331];
int findl(int x)
{
    if(f[x]==x)
        return x;
    return f[x]=findl(f[x]);
}
void mergel(int a,int b)
{
    int c=findl(a);
    int d=findl(b);
    if(c!=d)
        f[c]=d;
}
int main()
{
    int n,m,op,x,y;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        f[i]=i;//一定要注意开始的时候每个人的boss都是自己
    for(int i=0;i<m;i++)
    {
        cin>>op>>x>>y;
        if(op==1)
            mergel(x,y);
        else
        {
            int c=findl(x);
            int d=findl(y);
            if(f[c]!=f[d])
                cout<<"N"<<endl;
            else
                cout<<"Y"<<endl;

        }
    }

    return 0;
}

#如无特别声明,该文章均为 Shadowlove 原创,转载请遵循 署名-非商业性使用 4.0 国际(CC BY-NC 4.0) 协议,即转载请注明文章来源。
#最后编辑时间为: 2021 年 03 月 26 日


account_circle
email
explore


关于 DreamCat

主题名称:DreamCat | 版本:X1.9-20210218

主题开发:HanFengA7 | TeddyNight | Dev-Leo | CornWorld | WBStudio | 学神之女

Designed by HanFengA7 Power by Typecho

Copyright © 2015-2021 by LychApe All rights reserved!

加我的QQ
加我的微博
加我的支付宝
加我的微信
加我的QQ
加我的微博
加我的支付宝
加我的微信