并查集【模板】

标签: 算法总结

思路
并查集:树形数据结构
find函数(查找所有结点的根结点):

int find(int x){
    if(f[x]==x) return x;//如果结点本身就是根结点,直接返回自己
    else return f[x]=find(f[x]);//否则通过路径压缩递归返回根结点
}

关于find函数还有个路径压缩的知识点:

else return find(f[x]);//递归返回,一个个找它的父结点,最终找到根节点
else return f[x]=find(f[x]);//直接将结点连到其根节点上

第二个代码优化时间的方法就叫路径压缩
在这里插入图片描述
如图,求这棵树所有结点的祖先,时间复杂度取决于这棵树的深度,是O(n²)。
在这里插入图片描述
如图,求这棵树所有结点的祖先,时间复杂度取决于结点的个数,是O(n)。
∴路径压缩能优化时间复杂度

join函数(合并两个结点的根结点):

void join(int x,int y){
    f[find(x)]=find(y);//f数组用来存结点的祖先,通过find函数,合并两个结点x、y的根结点
    return;//合并后别忘了直接返回
}

判断(两个结点是否有共同根结点):

if(find(a)==find(b))
    cout<<"Y"<<endl;//如果结点a和b有相同的根结点,则输出“Y”
else
    cout<<"N"<<endl;//否则输出“N”

———————————————————————————————————————————————————————
【模板】
(注释版)

#include<bits/stdc++.h>
using namespace std;
int n,m,f[10010],a,b,c;//数组f[i]记录i的根结点
int find(int x){
    if(f[x]==x) return x;//如果结点本身就是根结点,直接返回自己
    else return f[x]=find(f[x]);//否则通过路径压缩递归返回根结点
}
void join(int x,int y){
    f[find(x)]=find(y);//通过find函数,合并两个结点x、y的根结点
    return;//合并后别忘了直接返回
}
int main(){//好习惯,直接从主函数读起
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        f[i]=i;//初始化根结点数组,确保每个结点现在的根结点都是自己
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        if(a==1)//a为1时进行合并操作
            join(b,c);//直接调用join()函数
        else
            if(find(b)==find(c))//当结点b、c的根结点相等时,则它们在一个集合里
                cout<<"Y"<<endl;
            else//否则它们不属于同一个集合
                cout<<"N"<<endl;
    }
    return 0;
}

(无注释版)

#include<bits/stdc++.h>
using namespace std;
int n,m,f[10010],a,b,c;
int find(int x){
    if(f[x]==x) return x;
    else return f[x]=find(f[x]);
}
void join(int x,int y){
    f[find(x)]=find(y);
    return;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        if(a==1)
            join(b,c);
        else
            if(find(b)==find(c))
                cout<<"Y"<<endl;
            else
                cout<<"N"<<endl;
    }
    return 0;
}

———————————————————————————————————————————————————————
总结
并查集分3步:
1. 把每个结点所在的集合初始化为它自己
2. 将两个不同集合的结点合并(join函数)
3. 查找结点所在集合的根结点(find函数)
———————————————————————————————————————————————————————
经典例题:
P3367
题目
题解

版权声明:本文为Integricode26原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Integricode26/article/details/107479618

智能推荐

说说 Python Django 应用的基础目录结构

通过以下 django-admin 指令创建应用之后,就会生成应用的基础目录结构。 比如,我们建立了一个叫 ‘first’ 的应用,它的目录结构是这样的: 目录或文件 说明 最外层的 first/ 这是新应用的根目录,所有与该应用相关的内容都放在这里。 manage.py 用于管理 Django 项目的命令行工具。 里面一层的 first/ 目录 是一个...

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

猜你喜欢

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...

力扣困难难度 第4题 寻找两个正序数组的中位数

先看一眼题 我的思路: 设置下标i,j分别用于遍历两个数组,初始值均为0,直到找到两个数组中从小到大的第第length/2个数为止结束循环,length为两个数组长度之和。 ·每次比较nums[i]nums[j],如果前者小则i++,否则j++ ·循环结束时,如果count已经达到length/2,则说明已经找到了中位数,[注意:此时有可能正好其中一个数组遍历完了!所以...