【算法笔记】并查集你了解吗？

前言： 最近发现了一个很有趣的算法，那就是并查集，如果你不了解什么是并查集的话，我希望你能看看下面的文章，因为它真的是一个十分有趣且有用的算法结构！

1. 并查集基本介绍

情景引入：

假设有 a、b、c、d、e、f 六个样本，首先设这几个小样本在自己的集合里 {a}、{b}、{c}、{d}、{e}、{f}，针对上述介绍有以下两个操作

• boolean isSameSet(a, e) ： 查询 a 和 e 两个样本是否在一个集合
• void union(a, e)： 将 a 所在的集合的全体和 e 所在的集合的全体变成一个集合

而使用并查集的作用就是，假设有 N 个这样的样本，如果频繁使用上述两个操作能够均摊下来后让时间复杂度为 O(1)

并查集的做法：

• 首先我们将含有这六个样本的集合都有一个指针来指向自己，并且规定，每个集合最上方的节点表示代表节点
• 当我们查询 a 和 b 样本是否在一个集合时，我们就比较这两个集合的代表节点是否一样，这里是不同的。
• 我们让 a 和 b 两个集合的全体合并成一个集合，就可以直接让 b 的指针指向 a
• 当我们再查询 b 和 c 样本是否在一个集合时，发现 b 样本的代表节点是 a，c 样本的代表节点是 b，故这两个样本并不在一个集合中。如果要合并，我们就可以将集合样本数少代表节点的指针指向集合样本数多的代表节点的指针
• 我们也很轻松的查询到，d 和 e 样本不在一个集合，我们也可以让他俩合并为一个集合
• 当我们查询 e 和 c 样本是否在一个集合时，发现 c 样本的代表节点时 a，e 样本的代表节点是 d，故 e 和 c 样本不在一个集合。当我们要合并这两个样本所在的集合时，就可以将 e 所在的集合的代表节点的指针指向 c 所在的集合的代表节点的指针

2. 并查集的实现（模板）

下面用并查集的方式，实现了上述情景的两种操作，并且保证了均摊的时间复杂度为 O(1)。可以通过数组代替 HashMap 来提高效率，因为 HashMap 中的常数是大常数

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

// 并查集的实现
public class UnionFind<V> { 
    // 节点
    public static class Node<V> { 
        V value;

        public Node(V value) { 
            this.value = value;
        }
    }

    // 用来存储每个集合的样本和节点
    public HashMap<V, Node<V>> nodes;
    // 用来存储子节点和父节点的对应关系（前子后父）
    public HashMap<Node<V>, Node<V>> parents;
    // 用来存储每个样本所在的集合的样本个数
    public HashMap<Node<V>, Integer> sizeMap;

    // 初始化并查集(values 表示样本值）
    public UnionFind(List<V> values) { 
        nodes = new HashMap<>();
        parents = new HashMap<>();
        sizeMap = new HashMap<>();
        for (V cur : values) { 
            Node<V> node = new Node<>(cur);
            nodes.put(cur, node);
            parents.put(node, node);
            sizeMap.put(node, 1);
        }
    }

    // 向上找到代表节点，并且该方法中还做了路径压缩，让该节点及以上的节点直接指向代表节点
    public Node<V> findFather(Node<V> cur) { 
        Stack<Node<V>> path = new Stack<>();
        while (cur != parents.get(cur)) { 
            path.add(cur);
            cur = parents.get(cur);
        }
        while (!path.isEmpty()) { 
            parents.put(path.pop(), cur);
        }
        return cur;
    }

    // 判断 a 和 b 样本是否在一个集合中
    public boolean isSameSet(V a, V b) { 
        return findFather(nodes.get(a)) == findFather(nodes.get(b));
    }

    // 将 a 和 b 样本所在的集合合并
    public void union(V a, V b) { 
        // 得到 a 和 b 样本的代表节点
        Node<V> aHead = findFather(nodes.get(a));
        Node<V> bHead = findFather(nodes.get(b));
        if (aHead != bHead) { 
            // 得到这两个集合的样本个数
            int aSize = sizeMap.get(aHead);
            int bSize = sizeMap.get(bHead);
            // 将得到的代表节点进行重定向
            // max 表示样本个数多的代表节点
            // min 表示样本个数少的代表节点
            Node<V> big = aSize > bSize ? aHead : bHead;
            Node<V> small = big == aHead ? bHead : aHead;
            parents.put(small, big);
            sizeMap.put(big, aSize + bSize);
            sizeMap.remove(small);
        }
    }
}

3. 题目

题一：有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i] [j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i] [j] = 0 表示二者不直接相连。返回矩阵中省份的数量。

方法： 本题运用并查集的思想，但与上述模板不同，这里将上述模板的 Map 改用数组实现，用数组实现其实效率会更高！

public static int findCircleNum(int[][] isConnected) { 
    int N = isConnected.length;
    UnionFind unionFind = new UnionFind(N);
    for (int i = 0; i < N; i++) { 
        for (int j = i + 1; j < N; j++) { 
            if (isConnected[i][j] == 1) { 
                unionFind.union(i, j);
            }
        }
    }
    return unionFind.sets();
}

public static class UnionFind { 

    // 表示父子节点关系 parents[i]=k i为子节点，k为父节点
    public int[] parents;
    // 表示含有当前节点的集合所有的节点数
    public int[] size;
    // 辅助节点，用于在压缩路径时充当栈
    public int[] help;
    // 集合的个数
    public int sets;

    public UnionFind(int N) { 
        parents = new int[N];
        size = new int[N];
        help = new int[N];
        sets = N;
        for (int i = 0; i < N; i++) { 
            parents[i] = i;
            size[i] = 1;
        }
    }

    public int findFather(int cur) { 
        int count = 0;
        while (cur != parents[cur]) { 
            help[count++] = cur;
            cur = parents[cur];
        }
        for (int i = 0; i < count; i++) { 
            parents[help[i]] = cur;
        }
        return cur;
    }

    public void union(int a, int b) { 
        int aHead = findFather(a);
        int bHead = findFather(b);
        if (aHead != bHead) { 
            int aSize = size[aHead];
            int bSize = size[bHead];
            int big = (aSize >= bSize) ? aHead : bHead;
            int small = (big == aHead) ? bHead : aHead;
            size[big] += size[small];
            parents[small] = big;
            sets--;
        }
    }

    public int sets() { 
        return sets;
    }
}

力扣链接： 省份数量

题二：岛问题：给定一个二维数组 matrix，里面的值不是1就是0，上、下、左、右相邻的1认为是一片岛，返回 matrix 中岛的数量

方法一（递归）： 可以从左往右从上往下依次遍历，如果该位置的值为0或2，我们就跳过；如果为1，则将该位置上下左右值为1的位置的值变成2，岛的数量加1，依次遍历完整个数组。重点点就是实现这个 inflect 感染方法来更改数组值为1位置的值

public static int numIslands(char[][] grid) { 
    int islands = 0;
    for (int i = 0; i < grid.length; i++) { 
        for (int j = 0; j < grid[0].length; j++) { 
            if (grid[i][j] == '1') { 
                islands++;
                infect(grid, i, j);
            }
        }
    }
    return islands;
}

public static void infect(char[][] grip, int i, int j) { 
    if (i < 0 || i == grip.length || j < 0 || j == grip[0].length || grip[i][j] != '1') { 
        return;
    }
    grip[i][j] = '2';
    infect(grip, i - 1, j);
    infect(grip, i + 1, j);
    infect(grip, i, j - 1);
    infect(grip, i, j + 1);
}

方法二（并查集）： 可以使用并查集的方法，我们只需要对每个数组位置进行左和上的 union，就可以求得岛的数量

public static int numIslands2(char[][] grid) { 
    UnionFind unionFind = new UnionFind(grid);
    // 对第一行遍历（用来为后面遍历排除边界条件，注意 0 0 位置不需要遍历，因为它没有左和上的位置）
    for(int i=1;i<grid[0].length;i++) { 
        if(grid[0][i]=='1'&&grid[0][i-1]=='1') { 
            unionFind.union(unionFind.index(0, i), unionFind.index(0, i-1));
        }
    }
    // 对第一列遍历（用来为后面遍历排除边界条件，注意 0 0 位置不需要遍历，因为它没有左和上的位置）
    for(int i=1;i<grid.length;i++) { 
        if(grid[i][0]=='1'&&grid[i-1][0]=='1') { 
            unionFind.union(unionFind.index(i, 0), unionFind.index(i-1, 0));
        }
    }
    // 对右下角遍历
    for(int i=1;i<grid.length;i++) { 
        for(int j=1;j<grid[0].length;j++) { 
            if(grid[i][j]=='1'&&grid[i][j-1]=='1') { 
                unionFind.union(unionFind.index(i, j), unionFind.index(i, j-1));    
            }
            if((grid[i][j]=='1'&&grid[i-1][j]=='1')) { 
                unionFind.union(unionFind.index(i, j), unionFind.index(i-1, j));
            }
        }
    }

    return unionFind.sets();
}

public static class UnionFind{ 
    // 子节点的父节点
    public int[] parents;
    // 含有该节点的集合的节点数
    public int[] size;
    // 辅助节点
    public int[] help;
    // 集合个数
    public int sets;
    // 数组列数
    public int col;

    public UnionFind(char[][] grid) { 
        col = grid[0].length;
        int N = col*grid.length;
        parents=new int[N];
        size=new int[N];
        help=new int[N];
        sets=0;
        for(int i=0;i<grid.length;i++) { 
            for(int j=0;j<col;j++) { 
                if(grid[i][j]=='1') { 
                    int index=index(i,j);
                    parents[index]=index;
                    size[index]=1;
                    sets++;
                }
            }
        }
    }

    public int findFather(int cur) { 
        int count=0;
        while(cur!=parents[cur]) { 
            help[count++]=cur;
            cur=parents[cur];
        }
        for(int i=0;i<count;i++) { 
            parents[help[i]]=cur;
        }
        return cur;
    }

    public int index(int i,int j) { 
        return i*col+j;
    }

    public void union(int i,int j) { 
        int iHead=findFather(i);
        int jHead=findFather(j);
        if(iHead!=jHead) { 
            int iSize=size[i];
            int jSize=size[j];
            int big= iSize>jSize?iHead:jHead;
            int small=big==iHead?jHead:iHead;
            parents[small]=big;
            size[big]+=size[small];
            sets--;
        }
    }

    public int sets() { 
        return sets;
    }
}

力扣链接： 岛屿数量I

题三：由 m 行和 n 列组成的二维网格图最初充满了水。我们可以执行一个 addLand 操作，将位置 (row, col) 的水变成陆地。给定要操作的位置列表，计算每个 addLand 操作后的岛屿数量。岛屿被水包围，通过水平或垂直连接相邻的陆地而形成。你可以假设网格的四边都被水包围着。

方法： 该题使用并查集，与题二不同的是，这题是将陆地给新增，然后求得新增岛屿的数量，岛屿的数量不是固定的。这里的做法和题二相仿，只不过增加了个动态的将新增的陆地进行岛屿数量确定的方法

public static List<Integer> numIslands(int m, int n, int[][] positions) { 
    UnionFind unionFind = new UnionFind(m, n);
    List<Integer> ans = new LinkedList<>();
    for (int[] position : positions) { 
        ans.add(unionFind.connect(position[0], position[1]));
    }
    return ans;
}

public static class UnionFind { 
    public int[] parents;
    public int[] size;
    public int[] help;
    public int sets;
    public int row;
    public int col;

    public UnionFind(int m, int n) { 
        row = m;
        col = n;
        sets = 0;
        parents = new int[row * col];
        size = new int[row * col];
        help = new int[row * col];
    }

    public int sets() { 
        return sets;
    }

    public int index(int i, int j) { 
        return i * col + j;
    }

    public int findFather(int cur) { 
        int count = 0;
        while (cur != parents[cur]) { 
            help[count++] = cur;
            cur = parents[cur];
        }
        for (int i = 0; i < count; i++) { 
            parents[help[i]] = cur;
        }
        return cur;
    }

    public void union(int i1, int j1, int i2, int j2) { 
        if (i1 < 0 || i1 == row || j1 < 0 || j1 == col || i2 < 0 || i2 == row || j2 < 0 || j2 == col) { 
            return;
        }
        int index1 = index(i1, j1);
        int index2 = index(i2, j2);
        if (size[index1] == 0 || size[index2] == 0) { 
            return;
        }
        int f1 = findFather(index1);
        int f2 = findFather(index2);
        if (f1 != f2) { 
            int size1 = size[index1];
            int size2 = size[index2];
            int big = size1 > size2 ? f1 : f2;
            int small = big == f1 ? f2 : f1;
            parents[small] = big;
            size[big] += size[small];
            sets--;
        }
    }

    public int connect(int i, int j) { 
        int index = index(i, j);
        if (size[index] == 0) { 
            parents[index] = index;
            size[index] = 1;
            sets++;

            union(i, j, i, j + 1);
            union(i, j, i - 1, j);
            union(i, j, i + 1, j);
            union(i, j, i, j - 1);
        }
        return sets;
    }
}

力扣链接： 岛屿数量II

题四：在题三的前提下，如果 matrix 极大，设计一种可行的并行计算方案

这里先简单的将一个矩形分一半来举例，示例图如下：

上述示例，1就表示岛屿，0表示海洋。如果不进行分割，那么岛屿的数量只有一个；如果进行分割，那么左边的岛屿数量是2，右边的岛屿数量也是2。

因此我们可以在分割后进行遍历后，将每个边界节点做一下记录，并给每个边界节点标好它自己的代表节点。当我们进行合并时，上述边界节点就分成了 a、b、c、d 四个集合，因此可以使用并查集，将这些集合进行合并，最终随着合并，岛屿的数量就变成了1个。

而对于 matrix 极大的情况，就可以进行多次分割，这时只要按照分割的方式，记录好边界点，并标好边界节点的代表节点，当合并时，使用并查集就可以依次合并！