算法笔记【2】 并查集_并查集2实验报告-程序员宅基地

技术标签: 算法  java  算法笔记  数据结构  

算法笔记【2】 并查集

并查集简介

并查集被很多OIer认为是最简洁而优雅的数据结构之一,主要用于解决一些元素分组的问题。它管理一系列不相交的集合,并支持两种操作:

  • 合并(Union):把两个不相交的集合合并为一个集合。
  • 查询(Find):查询两个元素是否在同一个集合中。

当然,这样的定义未免太过学术化,看完后恐怕不太能理解它具体有什么用。所以我们先来看看并查集最直接的一个应用场景:亲戚问题

题目背景
若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。
题目描述
规定: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号和3号比武,假设1号赢了(这里具体谁赢暂时不重要),那么3号就认1号作帮主*(合并1号和3号所在的集合,1号为代表元素)*。

在这里插入图片描述

现在2号想和3号比武*(合并3号和2号所在的集合),但3号表示,别跟我打,让我帮主来收拾你(合并代表元素)*。不妨设这次又是1号赢了,那么2号也认1号做帮主。

在这里插入图片描述

现在我们假设4、5、6号也进行了一番帮派合并,江湖局势变成下面这样:

在这里插入图片描述

现在假设2号想与6号比,跟刚刚说的一样,喊帮主1号和4号出来打一架(帮主真辛苦啊)。1号胜利后,4号认1号为帮主,当然他的手下也都是跟着投降了。

在这里插入图片描述

好了,比喻结束了。如果你有一点图论基础,相信你已经觉察到,这是一个状的结构,要寻找集合的代表元素,只需要一层一层往上访问父节点(图中箭头所指的圆),直达树的根节点(图中橙色的圆)即可。根节点的父节点是它自己。我们可以直接把它画成一棵树:

在这里插入图片描述

用这种方法,我们可以写出最简单版本的并查集代码。

初始化

class DisjointSetUnion {
    
    int[] f;

    public DisjointSetUnion(int n) {
    
        this.f = new int[n];
        for (int i = 0; i < n; i++) {
    
            this.f[i] = i;
        }
    }
}

假如有编号为1, 2, 3, …, n的n个元素,我们用一个数组f[]来存储每个元素的父节点(因为每个元素有且只有一个父节点,所以这是可行的)。一开始,我们先将它们的父节点设为自己。

查询

public int find(int x) {
    
    return f[x] == x ? x : find(f[x]);
}

我们用递归的写法实现对代表元素的查询:一层一层访问父节点,直至根节点(根节点的标志就是父节点是身)。要判断两个元素是否属于同一个集合,只需要看它们的根节点是否相同即可。

合并

public void merge(int i, int j){
    
    fa[find(i)] = find(j);
}

合并操作也是很简单的,先找到两个集合的代表元素,然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者,这里暂时不重要。本文末尾会给出一个更合理的比较方法。

路径压缩

最简单的并查集效率是比较低的。例如,来看下面这个场景:

在这里插入图片描述

现在我们要merge(2,3),于是从2找到1,fa[1]=3,于是变成了这样:

在这里插入图片描述

然后我们又找来一个元素4,并需要执行merge(2,4):

在这里插入图片描述

从2找到1,再找到3,然后fa[3]=4,于是变成了这样:

在这里插入图片描述

大家应该有感觉了,这样可能会形成一条长长的,随着链越来越长,我们想要从底部找到根节点会变得越来越难。

怎么解决呢?我们可以使用路径压缩的方法。既然我们只关心一个元素对应的根节点,那我们希望每个元素到根节点的路径尽可能短,最好只需要一步,像这样:

在这里插入图片描述

其实这说来也很好实现。只要我们在查询的过程中,把沿途的每个节点的父节点都设为根节点即可。下一次再查询时,我们就可以省很多事。这用递归的写法很容易实现:

public int find(int x) {
    
    return f[x] == x ? x : (f[x] = find(f[x]));
}

注意赋值运算符=的优先级没有三元运算符?:高,这里要加括号。

路径压缩优化后,并查集的时间复杂度已经比较低了,绝大多数不相交集合的合并查询问题都能够解决。然而,对于某些时间卡得很紧的题目,我们还可以进一步优化。

按秩合并

有些人可能有一个误解,以为路径压缩优化后,并查集始终都是一个菊花图(只有两层的树的俗称)。但其实,由于路径压缩只在查询时进行,也只压缩一条路径,所以并查集最终的结构仍然可能是比较复杂的。例如,现在我们有一棵较复杂的树需要与一个单元素的集合合并:

在这里插入图片描述

假如这时我们要merge(7,8),如果我们可以选择的话,是把7的父节点设为8好,还是把8的父节点设为7好呢?

当然是后者。因为如果把7的父节点设为8,会使树的深度(树中最长链的长度)加深,原来的树中每个元素到根节点的距离都变长了,之后我们寻找根节点的路径也就会相应变长。虽然我们有路径压缩,但路径压缩也是会消耗时间的。而把8的父节点设为7,则不会有这个问题,因为它没有影响到不相关的节点。

在这里插入图片描述

这启发我们:我们应该把简单的树往复杂的树上合并,而不是相反。因为这样合并后,到根节点距离变长的节点个数比较少。

我们用一个数组rank[]记录每个根节点对应的树的深度(如果不是根节点,其rank相当于以它作为根节点的子树的深度)。一开始,把所有元素的rank()设为1。合并时比较两个根节点,把rank较小者往较大者上合并。路径压缩和按秩合并如果一起使用,时间复杂度接近 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xJkeupH4-1611212170259)(https://www.zhihu.com/equation?tex=O%28n%29)] ,但是很可能会破坏rank的准确性。

值得注意的是,按秩合并会带来额外的空间复杂度,可能被一些卡空间的毒瘤题卡掉。

初始化(按秩合并)

class DisjointSetUnion {
    
    int[] f;
    int[] rank;

    public DisjointSetUnion(int n) {
    
        	this.rank = new int[n];
            this.f = new int[n];
            for (int i = 0; i < n; i++) {
    
                this.f[i] = i;
                this.rank[i] = 1;
            }
    }
}

合并(按秩合并)

inline void merge(int i, int j)
{
    
    int x = find(i), y = find(j);    //先找到两个根节点
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;                   //如果深度相同且根节点不同,则新的根节点的深度+1
}

为什么深度相同,新的根节点深度要+1?如下图,我们有两个深度均为2的树,现在要merge(2,5):

在这里插入图片描述

这里把2的父节点设为5,或者把5的父节点设为2,其实没有太大区别。我们选择前者,于是变成这样:

在这里插入图片描述

显然树的深度增加了1。另一种合并方式同样会让树的深度+1。

并查集的应用

在这里插入图片描述

大家看出这道题和并查集的关系了吗?

在这里插入图片描述

这是二维版本,题目中的三维版本是类似的

大家看看上面这张图,是不是看出一些门道了?我们把所有空洞划分为若干个集合,一旦两个空洞相交或相切,就把它们放到同一个集合中。

我们还可以划出2个特殊元素,分别表示底部顶部,如果一个空洞与底部接触,则把它与表示底部的元素放在同一个集合中,顶部同理。最后,只需要看顶部和底部是不是在同一个集合中即可。这完全可以通过并查集实现。来看代码:

public class Solution3958 {
    

    public static void main(String[] args) {
    
        // 高度
        int h = 10;
        // 半径
        int r = 3;
        // 圆点
        int[][] points = new int[][]{
    {
    1, 3, 2}, {
    1, 3, 3}, {
    2, 3, 4}, {
    3, 4, 4}, {
    3, 5, 12}};
        minCostConnectPoints(h, r, points);

    }

    public static void minCostConnectPoints(int h, int r, int[][] points) {
    
        //圆的个数
        int n = points.length;
        DisjointSetUnion disjointSetUnion = new DisjointSetUnion(n + 2);

        for (int i = 0; i < n; i++) {
    
            if (points[i][2] <= r) {
    
                // 与底部接触的圆点
                disjointSetUnion.unionSet(i, n);
            }
            if (points[i][2] + r >= h) {
    
                // 与顶部接触
                disjointSetUnion.unionSet(i, n + 1);
            }
        }

        // 找出所有相连的圆
        for (int i = 0; i < n; i++) {
    
            for (int j = i + 1; j < n; j++) {
    

                if (nextTo(points[i][0], points[i][1], points[i][2], points[j][0], points[j][1], points[j][2], r)) {
    
                    disjointSetUnion.unionSet(i, j);
                }

            }
        }

        System.out.println(disjointSetUnion.find(n) == disjointSetUnion.find(n + 1) ? "Yes" : "No");

    }

    /**
     * 是否相交或者相切
     */
    public static boolean nextTo(int x, int y, int z, int x1, int y1, int z1, int r) {
    
        return (x - x1) * (x - x1) + (y - y1) * (y - y1) + (z - z1) * (z - z1) <= 4 * r * r;
    }

    static class DisjointSetUnion {
    
        int[] f;
        int[] rank;
        int n;

        public DisjointSetUnion(int n) {
    
            this.n = n;
            this.rank = new int[n];
            Arrays.fill(this.rank, 1);
            this.f = new int[n];
            for (int i = 0; i < n; i++) {
    
                this.f[i] = i;
            }
        }

        /**
         * 找到传入x节点的root节点
         *
         * @param x 顶点
         * @return root节点
         */
        public int find(int x) {
    
            return f[x] == x ? x : (f[x] = find(f[x]));
        }

        /**
         * 判断传入的顶点是否在图中形成回路
         */
        public void unionSet(int x, int y) {
    
            // 找到 x y 的根节点位置 fx fy
            int fx = find(x), fy = find(y);

            // 比较fx和fy两个根节点的深度 把小的父节点设置给大的一个
            if (rank[fx] <= rank[fy]) {
    
                f[fx] = fy;
            } else {
    
                f[fy] = fx;
            }
            // 应为两个树的深度相同,所以合并后父节点的树深度会增加1
            if (rank[fx] == rank[fy] && fx != fy) {
    
                rank[fy]++;
            }
        }
    }
}

并查集的应用还有很多,例如最小生成树的Kruskal算法等。这里就不细讲了。总而言之,凡是涉及到元素的分组管理问题,都可以考虑使用并查集进行维护。

--------------最后感谢大家的阅读,愿大家技术越来越流弊!--------------

在这里插入图片描述

--------------也希望大家给我点支持,谢谢各位大佬了!!!--------------

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

智能推荐

web应用托管_自托管的免费发票应用-FusionInvoice-程序员宅基地

文章浏览阅读438次。web应用托管Note that around the exact time of this article’s publication, FusionInvoice 2 was released as commercial software, and is based on Laravel instead of CodeIgniter like previous versions. It is,..._]fusion怎么处理电子(非纸质)发票?

react 组件添加样式_如何通过4个简单的步骤将CSS模块样式表添加到React组件-程序员宅基地

文章浏览阅读252次。react 组件添加样式Let’s say you’d like to add a CSS Modules Stylesheet to your project. You can find Create React App’s guidance here, but essentially — and as the guidance states — CSS Modules let you use ..._react在自定义的组件上增加样式类

如何在Google和其他高科技公司获得软件工程师职位-程序员宅基地

文章浏览阅读510次。by YK Sugi 由YK Sugi 如何在Google和其他高科技公司获得软件工程师职位 (How to Get a Software Engineer Job at Google and Other Top Tech Companies)Hi everyone! 嗨,大家好! I’ve already talked about how I personally got a softw..._获得谷歌的软件工程师职位英语

steam密码查看_如何查看和清除Steam中的先前别名-程序员宅基地

文章浏览阅读3.5k次。steam密码查看Steam lets you set your name to anything within its terms of service. This can make it difficult to find people—even if they’re already on your friends list. Find out who’s who by checking al..._steam密码查看

spark和java类型转化时报错:Caused by: java.lang.ClassCastException: scala.collection.mutable_scala.collection.mutable.wrappedarray$ofref is not-程序员宅基地

文章浏览阅读1.3k次。错误:Caused by: java.lang.ClassCastException: scala.collection.mutable.WrappedArray$ofRef cannot be cast to java.util.List分析:这个问题,一般是在sparksql中做row转换时候出错,最好一步步排错。这里要说的是, row:Row是先做了一次强制类型转换(asInstanceOf),row的实际类型是Seq[T],但是不能用Array[T],否则就会出现各种scala和java的类_scala.collection.mutable.wrappedarray$ofref is not a valid external type for

kconfig_对自己的项目使用kconfig-程序员宅基地

文章浏览阅读1.3k次。kconfig 介绍 (Intro)Every Linux professional write scripts. Someеimes light, linear. Sometimes complex script with functions and libs(yes, you can write your bash-library for use in other scripts). 每个..._kconfig 应用程序

随便推点

golang 转换为字符串_在Golang中,如何将错误转换为字符串?-程序员宅基地

文章浏览阅读2.8k次,点赞2次,收藏2次。golang 转换为字符串In Golang, fmt.Println(err) can print out the error err. But how to convert an error to a string explicitely? 在Golang中, fmt.Println(err)可以打印出错误 err 。 但是如何将错误显式转换为字符串 ? In Go, the error t..._golang中错误转换为字符串的方法

解决正在等待响应_解决一些等待问题-程序员宅基地

文章浏览阅读4k次。解决正在等待响应 背景 (Background) On occasion, I’ll see waits that exceed what I expect well above normal and a few of them have some architecture and standards to consider following when troubleshooting, ..._正在等待某某某的响应

outlook邮件恢复字体_如何更改Outlook 2013中邮件列表中使用的字体大小-程序员宅基地

文章浏览阅读2.1k次。outlook邮件恢复字体Outlook 2013 allows you to customize the font used to display the sender’s name, subject, date received, and size of each message in your message list. Maybe you want to just change the s..._how to change the font size of outlook

使用django-social-auth获取用户数据-程序员宅基地

文章浏览阅读285次。Recently we had to add support for social networks login to an application we are developing and we chose django-social-auth to work with. It is a well documented and easy to use django application fo..._django social auth

vue带缩略图的轮播图插件_带有缩略图轮播的自适应图像库-程序员宅基地

文章浏览阅读2.5k次。vue带缩略图的轮播图插件View demo 查看演示Download Source 下载源Today we want to show you how to create a responsive image gallery with a thumbnail carousel using Elastislide. Inspired by Twitter’s ..._jquery 实现照片流

debian 查看日志_如何使用Debian 10上的日志集中日志-程序员宅基地

文章浏览阅读4.8k次。debian 查看日志 介绍 (Introduction)System logs are an extremely important component of managing Linux systems. They provide an invaluable insight into how the systems are working and also how they are bein..._debian中日志服务