朋友圈（547） https://leetcode-cn.com/problems/friend-circles/
冗余连接（684） https://leetcode-cn.com/problems/redundant-connection/
冗余连接 II（685） https://leetcode-cn.com/problems/redundant-connection-ii/
岛屿数量（200） https://leetcode-cn.com/problems/number-of-islands/
连通网络的操作次数（1319） https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/
表示数值的字符串（剑指 Offer 20） https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/
最大连通面积（面试题 16.19） https://leetcode-cn.com/problems/pond-sizes-lcci/
能否连接形成区域（面试题 16.19） https://leetcode-cn.com/problems/pond-sizes-lcci/
合并账户（721） https://leetcode-cn.com/problems/accounts-merge/
判断能否形成等差数列（1502） https://leetcode-cn.com/problems/can-make-arithmetic-progression-from-sequence/

以上是一些力扣上的并查集题目，建议在练习时，先自己尝试思考解法，如果卡在某个地方，可以查看题解或者向其他程序员求助。

二.三大操作

1.初始化

我们把数组初始化-1,具体的作用我们之后再来分析具体的用处,具体含义就是,这个负数的相反数为这棵树的高度-1

    public void init(int[] parent) {
        //初始值设置为-1
        for (int i = 0; i < parent.length; ++i) {
            parent[i] = -1;
        }

    }

2.查找

不进行路径压缩的查找简单粗暴的,它的目的就是为了找到结点i的根结点,直接看代码

    public int find(int[] parent, int i) {
        if (parent[i] < 0) {//当前结点为根结点,终止
            return i;
        } else {
            return parent[i];     //返回父节点
        }
    }

这个时候我们来研究一下进行路径压缩的查找方式,我们需要合并0和4,如果我们只是粗暴的合并的话,这个时候0指向3,这个时候其实的查询长度就是越来越长,时间复杂度为O(n)

所以这个时候我们不进行路径压缩,压缩之后的图是这样的,这个时候时间复杂度大大降低,我们每次查找根结点的时候,只需要查找一次(递归一次)便可以找到根结点

进行路径压缩的查找方法要进行两个操作,最终目的肯定还是要找寻到根结点,但是其次他也进行了路径的压缩,例如下图一样,把本来的4指向3,修改成了4指向了2,其实可以精炼成一句话:找到根结点,并且把路径上所有节点的父亲结点修改为根结点.这样树的高度就变成了1(只含有一个结点(根结点)的高度为0).

    public int find(int[] parent, int i) {
        if (parent[i] < 0) {//当前结点为根结点,终止
            return i;
        } else {
            parent[i] = find(parent, parent[i]);  //父节点设为根结点
            return parent[i];     //返回父节点
        }


    }

3.合并

合并操作也可以简单粗暴的进行合成,我们只需要找到各自的祖先,任意的将一个合并到另一个上边即可,直接看代码

    public void union(int[] parent, int i, int j) {
        int i_parent = find(parent, i);//寻找i的根结点
        int j_parent = find(parent, j);//寻找j的根结点
        parent[i_parent]=j_parent;//将根结点为i_parent的树合并到根结点j_parent上
    }

如果我们这个时候进行合并可能会出现这种情况,也就是一个高度较大的数合并到了一个高度较小的树上面,这个时候树的高度就会增加,如果我们是高度小的树合并到高度较大的树上边(两颗树的高度不相等),这个时候树的高度便不会增加,自然查找的时候会更加快速的查找到.

进行按秩(树的高度)进行合并

这种合并方式就是为了解决上面所提到的问题,合并是便会是这种情况,但是我们如果判断两棵树的高度大小呢,这个时候就可以解释以下初始化的为-1的目的了,一:如果当前结点的值为负数,可以判断当前结点为根结点,二.当前结点越小(也就是相反数越大),说明当前树的高度越大,我们只需要把更大的根结点的值合并到更小的根结点值上,便可以解决这个问题了.

这个时候存在一个特殊情况,也就是两棵树的高度一样高.这个时候无论如何进行合并,树的高度度会增加,因此这个时候我们可以把一个根结点合并到另一个根结点上,并把合并到的根结点的值减一

    public void union(int[] parent, int i, int j) {
        int i_parent = find(parent, i);//寻找i的根结点
        int j_parent = find(parent, j);//寻找j的根结点
        if (i_parent != j_parent) {//此时的根结点相同,没有合并的必要
            if (parent[i_parent] < parent[j_parent]) {//此时表示i_parent的秩比j_parent的秩大
                parent[j_parent] = i_parent;//把j_parent合并到i_parent上
            } else {
                if (parent[i_parent] == parent[j_parent]) {
                    parent[j_parent]--;
                }
                parent[i_parent] = j_parent;//把i_parent合并到j_parent上

            }

        }
    }

三.省份数量

1.题目描述

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

力扣:力扣

2.问题分析

这是一道很典型的并查集问题,题目的意思就是城市之间相连就是一个省份,把相连的城市合并为一颗树,最终就是寻找有多少个根结点(有多少颗树),也就是parent[i]有多少个是小于0的值,就是一棵树,最终返回数量就可以了

3.代码实现

    public void init(int[] parent) {
        //初始值设置为-1
        for (int i = 0; i < parent.length; ++i) {
            parent[i] = -1;
        }

    }

    public int find(int[] parent, int i) {
        if (parent[i]<0) {
            return i;
        } else {
            parent[i] = find(parent, parent[i]);  //父节点设为根结点
            return parent[i];     //返回父节点
        }


    }

    public void union(int[] parent, int i, int j) {
        int i_parent = find(parent, i);//寻找i的祖先
        int j_parent = find(parent, j);//寻找j的祖先
        if (i_parent != j_parent) {//此时的祖先相同,没有合并的必要
            if (parent[i_parent] < parent[j_parent]) {//此时表示i_parent的秩比j_parent的秩大
                parent[j_parent] = i_parent;//把j_parent合并到i_parent上
            } else {
                if (parent[i_parent] == parent[j_parent]) {
                    parent[j_parent]--;
                }
                parent[i_parent] = j_parent;//把i_parent合并到j_parent上

            }

        }
    }
    public int findCircleNum(int[][] isConnected) {
        int[] parent = new int[isConnected.length];
        init(parent);
        for (int i = 0; i < isConnected.length; ++i) {
            for (int j = i + 1; j < isConnected[0].length; ++j) {
                if (isConnected[i][j] == 1) {
                    union(parent, i, j);
                }
            }
        }
        int cnt = 0;
        for (int i = 0; i < parent.length; ++i) {
            if (parent[i] < 0)
                cnt++;

        }
        return cnt;
    

    }

四.冗余连接

1.题目描述

树可以看成是一个连通且无环的无向图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

力扣:力扣

2.问题分析

题目的意思就是不能出现环,也就是如果两个两个点已经连通了,这个时候不能再在这两个点添加一条边,这个时候就冗余了,我们都知道一个连通分量有n个顶点,n-1条边,而这道题一共有n条边,我们需要寻找的就是这一条冗余的边,当find(parent,i,j)的根结点一样的时候,这个时候这两个顶点之间的边一定是冗余的,找到这样的一条边即可.

3.代码实现

    public void init(int[] parent) {
        for (int i = 0; i < parent.length; ++i) {
            parent[i] = -1;
        }
    }

    public int find(int[] parent, int i) {
        if (parent[i] < 0)
            return i;
        else {
            parent[i] = find(parent, parent[i]);
            return parent[i];
        }
    }

    public void union(int[] parent, int i, int j) {
        int i_parent = find(parent, i);
        int j_parent = find(parent, j);
        if (i_parent != j_parent) {
            if (parent[i_parent] < parent[j_parent]) {
                parent[j_parent] = i_parent;
            } else {
                if (parent[i_parent] == parent[j_parent]) {
                    parent[j_parent]--;
                }
                parent[i_parent] = j_parent;
            }
        }
    }

    public int[] findRedundantConnection(int[][] edges) {
        int[] parent = new int[edges.length+1];
        init(parent);
        for (int i = 0; i < edges.length; ++i) {
            if (find(parent, edges[i][0]) != find(parent, edges[i][1])) {
                union(parent, edges[i][0], edges[i][1]);
            } else {
                return edges[i];
            }
        }
        return null;


    }

猜你喜欢

Jease 2.6发布 Java开源内容框架
EasyCVR对接华为iVS订阅摄像机和用户变更请求接口介绍
JVM调优总结：反思
【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
JVM调优总结：调优方法
前端面试【JavaScript】— typeof 是否能正确判断类型？
JVM调优总结：新一代的垃圾回收算法
前端面试【JavaScript】— instanceof 能否判断基本数据类型？
JVM调优总结：典型配置举例
前端面试【JavaScript】— 能不能手动实现一下 instanceof 的功能？
前端面试【JavaScript】— Object.is和=== 有什么区别？
JVM调优总结：分代垃圾回收详述
前端面试【JavaScript】— JS中类型转换有哪几种？
WPF开发入门尝试
前端面试【JavaScript】— == 和 ===有什么区别？
一个Java程序员对2011年的回顾
前端面试【JavaScript】— 对象转原始类型是根据什么流程运行的？
JVM调优总结：垃圾回收面临的问题
直接在代码里面对list集合进行分页
JVM调优总结：基本垃圾回收算法

zl程序教程

当前栏目

并查集(不相交集)详解

一.并查集

1.什么是并查集

2.并查集的基本操作

3.并查集的应用

4.力扣上的题目

二.三大操作

1.初始化

2.查找

3.合并

三.省份数量

1.题目描述

2.问题分析

3.代码实现

四.冗余连接

1.题目描述

2.问题分析

3.代码实现

相关文章