并查集（二）并查集的算法应用案例上

2021-08-04 21:11:28

直接看本文的，建议先看并查集（一）并查集的几种实现。并查集的题在力扣上都是中等题或者难度题，这个特殊的数据结构还有一些门槛

P261. 以图判树

力扣第261题 这道题应该算是最适合去理解并查集的 https://leetcode-cn.com/problems/graph-valid-tree/

题目

给定从 0 到 n-1 标号的 n 个结点，和一个无向边列表（每条边以结点对来表示），
请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。

示例 1：

输入: n = 5, 边列表 edges = [[0,1], [0,2], [0,3], [1,4]]
输出: true

示例 2:

输入: n = 5, 边列表 edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
输出: false

题意

我们首先要理解 一个合法有效的树结构的意思，关键在于什么样的结构是一个合法有效的树结构，这里给的边的列表是无向的，无向也很重要，这样你不用考虑节点遍历需要有方向性。

所有节点组成一棵树，所有节点都会连接到一起，连接到一个顶点上
是树结构，不能有环，来研究一下环的情况

  o a              o a
 / \   树         / \   图 
o   o b        c o — o b

前面是树，我们来考虑链接的点，连接点a、b，连通前它们各自的点处于的状态是 不连通的状态
再来看一下后面图中的b、c的情况，b和c在没有直接连接时，它们是不是已经处于连通的状态了，因为它们已经通过顶点a连通了

代码思路：通过并查集合并所有节点，如果成树满足两个条件

最后只剩下一株
合并两个点之前，连个点处于不连通的状态

这里我们拿之前最后一种路径压缩的，之前讲过的五种方法中，任意选一种都可以，只是通常都选择后面两种性能较好的。同时注意一下，这里我们还在并查集的类中加入了一个成员变量plant，把并查集看做多棵树的话，最开始所有节点没有合并，树的总数为元素个数size，合并一次，树就减少一棵，所以join方法中plant--;

并查集类

public class UFRankUnionCompressPath {


    int[] parent;
    int[] rank;//树的层数
    int plant;  //一共有多少株树

    public UFRankUnionCompressPath(int size) {
        plant = size;
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    private int findP(int x) {//查询操作，其实是查询  根节点
        if (x < 0 || x >= parent.length)
            return -1;  //或者直接抛出异常

        while (parent[x] != parent[parent[x]])
        //如果parent[x]==parent[parent[x]] 说明这颗树到了第二层，或者第一层
        //第一层 因为parent[x]=x所以有  parent[x]==parent[parent[x]]
        //第二层 因为第二层的parent是根节点 有： parent[x]= root  
        //所以有 parent[parent[x]]= parent[root]  而本身 parent[root]=root
        {
            // x = parent[x];  //
            parent[x] = parent[parent[x]]; //将下层节点往顶层提升，最终
        }
        return parent[x];
    }


    public void join(int a, int b) {
        int ap = findP(a);
        int bp = findP(b);
        if (ap != bp) {
            plant--;
            //a的层数越高，就将层数少的合并到层数高的上面
            if (rank[ap] > rank[bp])
                parent[bp] = ap;
            else if (rank[ap] < rank[bp]) {
                parent[ap] = bp;
            } else {
                //相同情况的话，随便就可以
                parent[ap] = bp;
                rank[bp]++;
            }
        }
    }

    public int getPlant() {
        return plant;
    }

    public boolean isJoined(int a, int b) { //两个节点是否是  连接的
        return findP(a) == findP(b);
    }
}

具体解题实现

class Solution {
    public boolean validTree(int n, int[][] edges) {
            UFRankUnionCompressPath uf = new UFRankUnionCompressPath (n);
            for (int[] edge : edges) {
                //连通前是断开状态
                if(uf.isJoined(edge[0],edge[1])){
                     return false;
                }
                uf.join(edge[0], edge[1]);
            }
            //最后连通只有一棵树
            return uf.getPlant()==1;    
    
        }
}

另外一种实现

除了上面这种实现，这里还有另外一种实现方式。如果是一棵树，边数和顶点数是满足以下关系的
边数 = 点数 - 1，具体的定理的证明你可以试试。在这种情况下，我们就不用去判断连接前是不连通的状态了，如果有边连接前是连通的，那它一定也不满足边数 = 点数 - 1

class Solution {
    public boolean validTree(int n, int[][] edges) {
        //树，首先要满足边数 = 点数 - 1，其次是保证联通。
        if (n < 1 || edges.length != n - 1) {
            return false;
        }

        UFRankUnionCompressPath uf = new UFRankUnionCompressPath (n);
        for (int[] edge : edges) {
            uf.join(edge[0], edge[1]);
        }
        
        return uf.getPlant()==1;

    }
}

695. 岛屿的最大面积

力扣第695题 这题比刚刚那道题稍微复杂了一点点，但理解了还是很简单的
https://leetcode-cn.com/problems/max-area-of-island/

题目

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 【岛屿】是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 
必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)


示例 1：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

输出：4

题意

题意是比较简单的，就是说挨着的1就能连接成陆地（但只在水平和锤子方向挨着，斜着不算），计算最大的陆地连接了几个点，如题中给出的案例，最大岛屿是数组左上角连接的4个数字。

解题思路

我们知道并查集是解决连通性的问题，那么可以这样用并查集连接上陆地的点，再通过计数算出该连通的树的节点数。我们又需要再次将之前的并查集做一定的修改，增加一个记录节点数的变量，因为是每个节点都有，使用数组记录。

class Solution {
     public int maxAreaOfIsland(int[][] grid) {

        int h = grid.length;
        int w = grid[0].length;
        UFRankUnionPlant uf = new UFRankUnionPlant(w * h);
        boolean noJoin = true;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                //int index = w * i + j;
                if (grid[i][j] == 1) {
                    noJoin = false;
                    //做合并操作
                    if (i - 1 >= 0 && grid[i - 1][j] == 1) {
                        //将二维数组点映射成一维的点
                        uf.join(w * (i - 1) + j, w * i + j);  
                    }

                    if (j - 1 >= 0 && grid[i][j - 1] == 1) {
                        uf.join(w * i + j - 1, w * i + j);
                    }
                }
            }
        }
        //特别注意，因为并查集的初始的len一定是1，但如果没产生任何合并，最大岛屿是0
        return  noJoin? 0:  uf.maxLen;  
    }
}

//基于并查集修改的类
public class UFRankUnionPlant {

    int[] parent;
    int[] rank;//树的层数
    int plant;//株
    int maxLen; //全局记录最大株的成员变量
    int[] len;  //记录每株数的节点数的数组

    public UFRankUnionPlant(int size) {
        parent = new int[size];
        rank = new int[size];
        len = new int[size];    //记录根的节点数
        plant = size;
        maxLen = 1;
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
            len[i] = 1;
        }
    }


    public int findP(int x) {//查询操作，其实是查询  根节点
        if (x < 0 || x >= parent.length)
            return -1;  //或者直接抛出异常

        while (parent[x] != x)//一直搜索到根节点
            x = parent[x];

        return x;
    }


    public void join(int a, int b) {
        int ap = findP(a);
        int bp = findP(b);
        if (ap != bp) {
            plant--;
            //a的层数越高，就将层数少的合并到层数高的上面
            int joinlen = len[ap] + len[bp];
            maxLen = Math.max(joinlen, maxLen);

            if (rank[ap] > rank[bp]) {
                parent[bp] = ap;
                len[ap] = joinlen;
            } else if (rank[ap] < rank[bp]) {
                parent[ap] = bp;
                len[bp] = joinlen;
            } else {
                //相同情况的话，随便就可以
                parent[ap] = bp;
                rank[bp]++;
                len[bp] = joinlen;
            }
        }
    }

    public int getPlant() {
        return plant;
    }

    public boolean isJoined(int a, int b) { //两个节点是否是  连接的
        return findP(a) == findP(b);
    }


}

码农公寓