本文共 9227 字，大约阅读时间需要 30 分钟。

并查集

并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（Union-find Algorithm）定义了两个用于此数据结构的操作：

• Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
• Union：将两个子集合并成同一个集合。

由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（Union-find Data Structure）或合并-查找集合（Merge-find Set）。

为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表（父/根节点），以表示整个集合。接着，Find(x)Find(x) 返回 xx 所属集合的代表，而 Union 使用两个集合的代表作为参数。

并查集常常用来判断在一个图中是否存在回路（是否可以生成树），以及用来判断图的连通性问题。

并查集的一种简单且使用较多的一种实现方法——快速union，快速find，基于重量的并查集实现方法。

很明显，并查集的时间复杂度是由树的深度决定的，跟二叉搜索树一致，O(h)，h是树的深度，二叉搜索树的时间复杂度是O(log n)，等比二分。

并查集并不是二叉树，而是多叉树，查询是其中一个分支，所以并查集的查询和合并时间复杂度并不是O(log n)。

在加上rank和路径压缩优化后，并查集的时间复杂度为O(log* n)，比O(log n)更优。

代码模板：

大小优化，适用于需要节点数的场景：

import java.util.Arrays;/** * Title：并查集模板 * Description： * @author WZQ * @version 1.0.0 * @date 2021/3/9 */public class UnionFind01 {
       /**     * 节点的代表，值父根节点的索引，索引是本节点     */    int[] parent;    /**     * 存放代表有多少的子节点     */    int[] size;    /**     * 初始化     * @param n     */    public UnionFind01(int n){
           parent = new int[n];        size = new int[n];        //一开始都指向自己        for (int i = 0; i < n; i++) {
               parent[i] = i;        }        Arrays.fill(size, 1);    }    /**     * 查找一个节点的代表     * @param x     * @return     */    public int find(int x){
           // 已经是根节点代表        if (parent[x] == x){
               return x;        }        // 递归查找根代表        return find(parent[x]);    }    /**     * x节点和y结点对应的图合并成一个图     * @param x     * @param y     */    public void union(int x, int y){
           int rootX = find(x), rootY = find(y);        // 同一个图        if (rootX == rootY) {
               return;        }        // 优化，让结点数小的图作为结点多的图的分支        // 如果结点多的图作为分支，那它find的时候会很耗时        if (size[rootX] <= size[rootY]){
               // 合并，rootX的父结点为rootY            parent[rootX] = rootY;            size[rootY] += size[rootX];        }else{
               parent[rootY] = rootX;            size[rootX] += size[rootY];        }    }}

深度优化：

import java.util.Arrays;/** * Title：并查集模板 * Description： * @author WZQ * @version 1.0.0 * @date 2021/3/9 */public class UnionFind02 {
       /**     * 节点的代表，值父根节点的索引，索引是本节点     */    int[] parent;    /**     * 存放根结点的深度     * 优化合并，深度大的作为父节点，深度不变     * 这样find的时候次数减少，由深度决定     */    int[] rank;    /**     * 初始化     * @param n     */    public UnionFind02(int n){
           parent = new int[n];        rank = new int[n];        //一开始都指向自己        for (int i = 0; i < n; i++) {
               parent[i] = i;        }        Arrays.fill(rank, 1);    }    /**     * 查找一个节点的代表     * @param x     * @return     */    public int find(int x){
           // 已经是根节点代表        if (parent[x] == x){
               return x;        }        // 递归查找根代表        return find(parent[x]);    }    /**     * x节点和y结点对应的图合并成一个图     * @param x     * @param y     */    public void union(int x, int y){
           int rootX = find(x), rootY = find(y);        // 同一个图        if (rootX == rootY) {
               return;        }        // 优化合并，让深度大的图作为根，深度小的作为分支        if (rank[rootX] < rank[rootY]){
               parent[rootX] = rootY;        }else if (rank[rootX] > rank[rootY]){
               parent[rootY] = rootX;        }else {
               // 相等，才需要维护rank            parent[rootX] = rootY;            rank[rootY] ++;        }    }}

import java.util.Arrays;import java.util.HashMap;import java.util.Map;/** * Title：leetcode-128-最长连续序列128-最长连续序列 * 
 * 并查集实现 * 
 * 给定一个未排序的整数数组 nums ， * 找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 * 
 * 输入：nums = [100,4,200,1,3,2] * 输出：4 * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 * 
 * Description： * * @author WZQ * @version 1.0.0 * @date 2021/3/9 */public class Main128 {
       public int longestConsecutive(int[] nums) {
           UnionFind uf = new UnionFind(nums.length);        Map
    
      map = new HashMap<>();        for (int i = 0; i < nums.length; i++) {
               if (map.containsKey(nums[i])) {
                   continue;            }            map.put(nums[i], i);            // 相邻的合并，连续            if (map.containsKey(nums[i] + 1)) {
                   uf.union(i, map.get(nums[i] + 1));            }            if (map.containsKey(nums[i] - 1)) {
                   uf.union(i, map.get(nums[i] - 1));            }        }        return uf.findMax();    }}class UnionFind {
       /**     * 节点的代表，值父根节点的索引，索引是本节点     */    int[] parent;    /**     * 存放代表有多少的子节点     */    int[] size;    /**     * 初始化     *     * @param n     */    public UnionFind(int n) {
           parent = new int[n];        size = new int[n];        //一开始都指向自己        for (int i = 0; i < n; i++) {
               parent[i] = i;        }        Arrays.fill(size, 1);    }    /**     * 查找一个节点的代表     *     * @param x     * @return     */    public int find(int x) {
           // 已经是根节点代表        if (parent[x] == x) {
               return x;        }        // 递归查找根代表        return find(parent[x]);    }    /**     * x节点和y结点对应的图合并成一个图     *     * @param x     * @param y     */    public void union(int x, int y) {
           int rootX = find(x), rootY = find(y);        // 同一个图        if (rootX == rootY) {
               return;        }        // 优化，让结点数小的图作为结点多的图的分支        // 如果结点多的图作为分支，那它find的时候会很耗时        if (size[rootX] <= size[rootY]) {
               // 合并，rootX的父结点为rootY            parent[rootX] = rootY;            size[rootY] += size[rootX];        } else {
               parent[rootY] = rootX;            size[rootX] += size[rootY];        }    }    /**     * 最大结点的图     *     * @return     */    public int findMax() {
           int max = 0;        for (int i = 0; i < size.length; i++) {
               max = Math.max(max, size[i]);        }        return max;    }}
    

import java.util.Arrays;/** * Title：leetcode-684 冗余连接 * Description：并查集 * 根代表一样说明都在同一个图中，相连的话会形成回路 * @author WZQ * @version 1.0.0 * @date 2021/3/9 */public class Main684 {
       public int[] findRedundantConnection(int[][] edges) {
           int[] result = new int[2];        if (edges == null || edges[0] == null){
               return result;        }        // 边数，顶点数        int length = edges.length;        // 并查集        UnionFind uf = new UnionFind(length);        for (int i = 0; i < length; i++) {
               // 1开始，数组都要减去1            // 形成回路则是结果            if (uf.find(edges[i][0] - 1) == uf.find(edges[i][1] - 1)){
                   result =  edges[i];            }            // 合并            uf.union(edges[i][0] - 1, edges[i][1] - 1);        }        return result;    }    class UnionFind{
           int[] parent;        int[] rank;        public UnionFind(int n){
               parent = new int[n];            rank = new int[n];            for (int i = 0; i < n; i++) {
                   parent[i] = i;            }            Arrays.fill(rank,1);        }        public int find(int x){
               if (parent[x] == x){
                   return x;            }            return find(parent[x]);        }        public void union(int x, int y){
               int rootX = find(x), rootY = find(y);            if (rootX == rootY){
                   return;            }            if (rank[rootX] > rank[rootY]){
                   parent[rootY] = rootX;            }else if (rank[rootX] < rank[rootY]){
                   parent[rootX] = rootY;            }else {
                   // 相等                parent[rootX] = rootY;                rank[rootY] ++;            }        }    }}

/** * Title：990. 等式方程的可满足性 * * 输入：["a==b","b!=a"] * 输出：false * 解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。 * * 输入：["c==c","b==d","x!=z"] * 输出：true * * * Description：并查集 * @author WZQ * @version 1.0.0 * @date 2021/3/24 */public class Main990 {
       public boolean equationsPossible(String[] equations) {
           int length = equations.length;        UnionFind unionFind = new UnionFind();        for (int i = 0; i < length; i++) {
               if (equations[i].charAt(1) == '='){
                   // 相等，需要合并，表示该图都相同                unionFind.union(equations[i].charAt(0) - 'a',                        equations[i].charAt(3) - 'a');            }        }        for (int i = 0; i < length; i++) {
               if (equations[i].charAt(1) == '!'){
                   // 不相同，判断是否在一个图中                int x = unionFind.find(equations[i].charAt(0) - 'a');                int y = unionFind.find(equations[i].charAt(3) - 'a');                // 在一个图上说明已有相等的前提                if (x == y){
                       return false;                }            }        }        return true;    }}class UnionFind{
       int[] parent;    int[] rank;    // 小写字母26个    public UnionFind(){
           parent = new int[26];        rank = new int[26];        for (int i = 0; i < 26; i++) {
               parent[i] = i;            rank[i] = 1;        }    }    public int find(int k){
           if (parent[k] == k){
               return parent[k];        }        return find(parent[k]);    }    public void union(int a, int b){
           int x = find(a);        int y = find(b);        if (x == y){
               return;        }        if (rank[x] > rank[y]){
               parent[y] = x;        }else if (rank[x] < rank[y]){
               parent[x] = y;        }else {
               // 深度相同才加1            parent[x] = y;            rank[y] ++;        }    }}

转载地址：http://nviwi.baihongyu.com/