首页 > 其他分享 >并查集

并查集

时间:2024-02-23 22:00:34浏览次数:34  
标签:int 查集 find 编号 集合 节点 op

作用:
1.将两个集合合并
2.询问两个元素是否在一个集合当中

基本原理:
每个集合用一棵树来表示,树根的编号就是整个集合的编号。每个节点存储它的父节点,p[x]表示x的父节点

操作:
1.判断树根:
if(p[x]==x);

2.求x的集合编号:
while(p[x]!=x) x=p[x];

3.如何合并两个集合:
p[x]是x的集合编号,py是y的集合编号。p[x]=y;

优化:
路径压缩~o(1);

AcWing-836

AC代码:

#include <iostream>

using namespace std;

const int N=1e5+10;

int a,b;
char op[2];//操作
int n,m;
int p[N];//存储父节点

int find(int x)//返回节点祖宗
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    cin>>n>>m;
    
    for(int i=1;i<=n;i++) p[i]=i;//初始化每一个节点是一个集合 所以自己就是祖宗
    
    while(m--)
    {
        cin>>op>>a>>b;
        if(op[0]=='M') p[find(a)]=find(b);//让编号a的集合 认集合b祖宗当爹
        else
        {
            if(find(a)==find(b)) cout<<"Yes"<<endl;//两集合祖宗相等
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

标签:int,查集,find,编号,集合,节点,op
From: https://www.cnblogs.com/Eric0521/p/18030447

相关文章

  • ABC302Ex Ball Collector (可撤销并查集)
    由于博客园存在关站风险,文章以后同步发在这里,可能会有更好的阅读体验。首先我们分析一下,如果我们已经知道了要走哪些点,我们可以怎么做。考虑将\(a_i,b_i\)之间连边,发现题目可以被转化为给定一个图,要求对于每条边将其一个顶点染色,问最多能将多少个点染色。于是我们对于每个连......
  • P3367 【模板】并查集
    原题链接并查集模板练手。递归版本#include<bits/stdc++.h>usingnamespacestd;constintN=1e4+5;intfather[N];intfind(intmid){if(father[mid]!=mid){father[mid]=find(father[mid]);}returnfather[mid];}voidunion_fa(intx,inty){......
  • 集合问题——并查集
    目录问题引入算法原理参考代码问题引入给出n个人的m个关系,表示给出的两个人都是朋友关系,之后进行k次询问,要求判断给出的两人是否是朋友关系,朋友的朋友也是朋友算法原理简单来说就是对集合的合并进行一个处理,使得是朋友的一群人用一个共同的朋友记录,这样在查询的时候就可以通过......
  • 连续性区间位置查询——链式并查集
    目录问题概述思路分析参考代码做题总结问题概述这里给出两个题目,一个是上一篇的新春漫步(其实当时给的官方题解就是链式并查集的写法,但是当时我懒得写了,emmm),二是最近vp的一场cf_div3_923场的d题,准确来说,就是因为这个我才准备写这个的,题目大概就是给出一个长度为n的数组和q组询......
  • 并查集
    一、并查集的概念并查集是一种管理元素分组情况的数据结构,主要实现以下两个功能:查询元素\(a\)和\(b\)是否在同一集合合并元素\(a\)和\(b\)所在的集合注:并查集只能进行合并操作,不能进行分割操作。二、并查集的实现一般,我们采用数组par[]和height[]来实现并查......
  • 并查集
    【并查集是什么】并查集是用来表示一些不相交集合的算法。它可以很快地处理两个点之间是否在一个连通块中。【并查集的特点】动态合并集合;合并之后就不能拆开了。并查集开始前,先按顺序把初始集合编号。(初始也不一定每个都是单个元素)【并查集的实现】数据结构分类:抽......
  • 并查集
    记录21:042024-2-3目录1.并查集题目记录1.并查集用来快速元素是否属于同一组的数据结构利用路径压缩和按秩合并防止结构退化点击查看代码#defineMAX_N10000intpar[MAX_N];intrank[MAX_N];voidinit(intn){for(inti=0;i<n;i++){par[i]=......
  • 并查集入门1【L2】
    讲义 引例1•有N个计算机中心,开始时都是独立的。后来不断的架设了M条网线,每条网线把其中的2个计算机中心连接起来。•直接或间接连接的计算机中心都可以相互通信,组成一个网络。 •问有多少个连通网络?  引例2•围棋的棋子有黑色和白色两种,相同颜色的棋子如果是上下......
  • POJ1182 食物链 (并查集的应用)
    POJ1182食物链(并查集的应用)Description动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B,B吃C,C吃A。现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述:第一种说法......
  • POJ2492 (并查集)
    POJ2492(并查集)题目:假设昆虫之间是异性互动,给出昆虫的互动情况,判断假设是否成立;输入:第一行t表示n个测试用例,每个测试用例第一行n,m表示n只昆虫,从1连续编号,m组互动情况;输出:假设不成立:Suspiciousbugsfound!假设成立:Nosuspiciousbugsfound!题解:参考POJ1611#include<cstdio......