Nine Chapter
  • Introduction
    • Summary
  • 1.Binary Search
    • Introduction
    • 458.Last position of target
    • 600.Smallest Rectangle Enclosing Black Pixels
    • 585.Maximum Number in Mountain Sequence
    • 183.Wood Cut
    • 62.Search in Rotated Sorted Array
    • 63.Search in Rotated Sorted Array II
    • 159.Find Minimum in Rotated Sorted Array
    • 160.Find Minimum in Rotated Sorted Array II
    • 75.Find Peak Element
    • 60.Search Insert Position
    • 28.Search a 2D Matrix
    • 240. Search a 2D Matrix II
    • 14.First Position of Target
    • 74.First Bad Version
    • 875. Koko Eating Bananas
    • 1011. Capacity To Ship Packages Within D Days (M)
    • 410. Split Array Largest Sum (H)
    • 475. Heaters (M)
    • 1044. Longest Duplicate Substring (H)
  • 2.Binary Tree
    • Summary
      • 二叉树八股文:递归改迭代
      • BST
      • Frame
    • 66.Binary Tree Preorder Traversal
    • 67.🌟Binary Tree Inorder Traversal
    • 145. Binary Tree Postorder Traversal (E)
    • 98.Validate Binary Search Tree(M)
    • 85.Insert Node in a Binary Search Tree
    • 104. Maximum Depth of Binary Tree(E)
    • 235. Lowest Common Ancestor of a Binary Search Tree (E)
    • 236.Lowest Common Ancestor of Binary Tree(M)
    • 578.Lowest Common Ancestor III
    • 1120.Subtree with Maximum Average
    • 596.Minimum Subtree
    • 480.Binary Tree Paths
    • 453.Flatten Binary Tree to Linked List
    • 110.Balanced Binary Tree
    • 376.Binary Tree Path Sum
    • 246.Binary Tree Path Sum II
    • 475.Binary Tree Maximum Path Sum II
    • 124.Binary Tree Maximum Path Sum (H)
    • Path Sum (*)
      • 112. Path Sum
      • 113. Path Sum II
      • 437. Path Sum III
    • 177.Convert Sorted Array to Binary Search Tree With Minimal Height
    • 7.Binary Tree Serialization
    • 72,73.Construct Binary Tree
    • Binary Search Tree Path
    • 245.Subtree
    • 469.Identical Binary Tree
    • 87.Remove Node in Binary Search Tree
    • 116.Populating Next Right Pointers in Each Node (M)
    • 114. Flatten Binary Tree to Linked List(M)
    • 654.Maximum Binary Tree (M)
    • 105. 🌟Construct Binary Tree from Preorder and Inorder Traversal (M)
    • 106. Construct Binary Tree from Inorder and Postorder Traversal (M)
    • 652. Find Duplicate Subtrees(M)
    • 230. Kth Smallest Element in a BST (M)
    • 538&1038. Convert BST to Greater Tree
    • 450. Delete Node in a BST (M)
    • 701. Insert into a Binary Search Tree (M)
    • 96. Unique Binary Search Trees
    • 95. Unique Binary Search Trees II (M)
    • 1373. Maximum Sum BST in Binary Tree (H)
    • 297. Serialize and Deserialize Binary Tree (H)
    • 222. Count Complete Tree Nodes (M)
    • 1120. Maximum Average Subtree
    • 341. Flatten Nested List Iterator
    • 333. Largest BST Subtree (M)
    • 543. Diameter of Binary Tree
    • Binary Tree Longest Consecutive Sequence(*)
      • 298.Binary Tree Longest Consecutive Sequence
      • 549. Binary Tree Longest Consecutive Sequence II (M)
  • 3.Breadth First Search
    • Introduction
      • BFS 算法解题套路框架
      • 双向 BFS 优化
    • 102.Binary Tree Level Order Traversal (M)
    • 103. Binary Tree Zigzag Level Order Traversal (M)
    • 107.Binary Tree Level Order Traversal II(M)
    • 618.Search Graph Nodes
    • 207.Course Schedule (M)
    • 210.Course Schedule II (M)
    • 611.Knight Shortest Path
    • 598.Zombie in Matrix
    • 133.Clone Graph (M)
    • 178.Graph Valid Tree
    • 7.Binary Tree Serialization
    • 574.Build Post Office
    • 573.Build Post Office II
    • 127.Topological Sorting
    • 127.Word Ladder
    • 126. Word Ladder II
    • (LeetCode)515.Find Largest Value in Each Tree Row
    • 111. Minimum Depth of Binary Tree (E)
    • 752. Open the Lock
    • 542. 01 Matrix (M)
    • 1306. Jump Game III (M)
  • 4.Depth First Search+BackTracking
    • Summary
      • FloodFill 算法
    • 136.Palindrome Partitioning
    • 39.Combination Sum
    • 40.Combination Sum II
    • 377. Combination Sum IV
    • 77.Combinations (M)
    • 78.Subsets (M)
    • 90.Subsets II (M)
    • 46.🌟Permutations
    • 47.Permutations II
    • 582.Word Break II
    • 490.The Maze (M)
    • 51.N-Queens (H)
    • 52. N-Queens II (H)
    • 698. Partition to K Equal Sum Subsets (M)
    • 22. Generate Parentheses (M)
    • 岛屿问题
      • 200.Number of Islands (M)
      • 1254. Number of Closed Islands (M)
      • 1020. Number of Enclaves (M)
      • 695. Max Area of Island (M)
      • 1905. Count Sub Islands (M)
      • 694. Number of Distinct Islands
    • 131. Palindrome Partitioning (M)
    • 967. Numbers With Same Consecutive Differences (M)
    • 79. Word Search (M)
    • 212. Word Search II (M)
    • 472. Concatenated Words (H)
    • Page 2
    • 291. Word Pattern II
    • 17. Letter Combinations of a Phone Number (M)
  • 5.LinkedList
    • Summary
      • 单链表的倒数第 k 个节点
      • Merge two/k sorted LinkedList
      • Middle of the Linked List
      • 判断链表是否包含环
      • 两个链表是否相交 Intersection of Two Linked Lists
      • 递归反转链表
      • 如何判断回文链表
    • 599.Insert into a Cyclic Sorted List
    • 21.Merge Two Sorted Lists (E)
    • 23.Merge k Sorted Lists (H)
    • 105.Copy List with Random Pointer
    • 141.Linked List Cycle (E)
    • 142.Linked List Cycle II (M)
    • 148.Sort List (M)
    • 86.Partition List (M)
    • 83.Remove Duplicates from Sorted List(E)
    • 82.Remove Duplicates from Sorted List II (M)
    • 206.Reverse Linked List (E)
    • 92.Reverse Linked List II (M)
    • 143.Reorder List (M)
    • 19.Remove Nth Node From End of List (E)
    • 170.Rotate List
    • 🤔25.Reverse Nodes in k-Group (H)
    • 452.Remove Linked List Elements
    • 167.Add Two Numbers
    • 221.Add Two Numbers II
    • 876. Middle of the Linked List (E)
    • 160. Intersection of Two Linked Lists (E)
    • 234. Palindrome Linked List (E)
    • 2130. Maximum Twin Sum of a Linked List (M)
  • 6.Array
    • Summary
      • 前缀和思路PrefixSum
      • 差分数组 Difference Array
      • 双指针Two Pointers
      • 滑动窗口算法算法
      • Sliding windows II
      • 二分搜索Binary Search
      • 排序算法
      • 快速选择算法
    • 604.Window Sum
    • 138.Subarray Sum
    • 41.Maximum Subarray
    • 42.Maximum Subarray II
    • 43.Maximum Subarray III
    • 620.Maximum Subarray IV
    • 621.Maximum Subarray V
    • 6.Merge Two Sorted Arrays
    • 88.Merge Sorted Array
    • 547.Intersection of Two Arrays
    • 548.Intersection of Two Arrays II
    • 139.Subarray Sum Closest
    • 65.Median of two Sorted Arrays
    • 636.132 Pattern
    • 402.Continuous Subarray Sum
    • 303. Range Sum Query - Immutable (E)
    • 304.Range Sum Query 2D - Immutable (M)
    • 560. Subarray Sum Equals K (M)
    • 370. Range Addition(M)
    • 1109. Corporate Flight Bookings(M)
    • 1094. Car Pooling (M)
    • 76. Minimum Window Substring(H)
    • 567. Permutation in String (M)
    • 438. Find All Anagrams in a String(M)
    • 3. Longest Substring Without Repeating Characters (M)
    • 380. Insert Delete GetRandom O(1) (M)
    • 710. Random Pick with Blacklist (H)
    • 528. Random Pick with Weight (M)
    • 26. Remove Duplicates from Sorted Array (E)
    • 27. Remove Element (E)
    • 283. Move Zeroes (E)
    • 659. Split Array into Consecutive Subsequences (M)
    • 4. Median of Two Sorted Arrays (H)
    • 48. Rotate Image (M)
    • 54. Spiral Matrix (M)
    • 59. Spiral Matrix II (M)
    • 918. Maximum Sum Circular Subarray
    • 128. Longest Consecutive Sequence (M)
    • 238. Product of Array Except Self (M)
    • 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (M)
    • 1151. Minimum Swaps to Group All 1's Together (M)
    • 2134. Minimum Swaps to Group All 1's Together II
    • 2133. Check if Every Row and Column Contains All Numbers
    • 632. Smallest Range Covering Elements from K Lists (H)
    • 36. Valid Sudoku (M)
    • 383. Ransom Note
    • 228. Summary Ranges
  • 7.Two pointers
    • Summary
      • Two Sum
      • 2Sum 3Sum 4Sum 问题
    • 1.Two Sum I
    • 170.Two Sum III - Data structure design
    • 167.Two Sum II- Input array is sorted
    • 609.Two Sum - Less than or equal to target
    • 610.Two Sum - Difference equals to targe
    • 587.Two Sum - Unique pairs
    • 533.Two Sum - Closest to target
    • 443.Two Sum - Greater than target
    • 653. Two Sum IV - Input is a BST (M)
    • 57.3Sum
    • 59.3Sum Closest
    • 58.4Sum
    • 148.Sort Colors
    • 143.Sort Colors II
    • 31.Partition Array
    • 625.Partition Array II
    • 382.Triangle Count
      • 611. Valid Triangle Number
    • 521.Remove Duplicate Numbers in Array
    • 167. Two Sum II - Input Array Is Sorted (E)
    • 870. Advantage Shuffle (M)
    • 9. Palindrome Number (E)
    • 125. Valid Palindrome(E)
    • 5. Longest Palindromic Substring (M)
    • 42. Trapping Rain Water
    • 11. Container With Most Water (M)
    • 658. Find K Closest Elements (M)
    • 392. Is Subsequence
  • 8.Data Structure
    • Summary
      • 数据结构的存储方式
      • 单调栈
      • 单调队列
      • 二叉堆 Binary Heap
      • TreeMap
      • TreeSet
      • 🌟Trie
      • Trie Application
    • 155. Min Stack (E)
    • 716. Max Stack (E)
    • 1648. Sell Diminishing-Valued Colored Balls
    • 232. Implement Queue using Stacks (E)
    • 225. Implement Stack using Queues(E)
    • 84.Largest Rectangle in Histogram
    • 128.Hash Function
    • Max Tree
    • 544.Top k Largest Numbers
    • 545.Top k Largest Numbers II
    • 613.High Five
    • 606.Kth Largest Element II
    • 5.Kth Largest Element
    • 129.Rehashing
    • 4.Ugly Number II
    • 517.Ugly Number
    • 28. Implement strStr()
    • 594.strStr II
    • 146.LRU Cache
    • 460.LFU Cache
    • 486.Merge k Sorted Arrays
    • 130.Heapify
    • 215. Kth Largest Element in an Array (M)
    • 612.K Closest Points
    • 692. Top K Frequent Words
    • 347.Top K Frequent Elements
    • 601.Flatten 2D Vector
    • 540.Zigzag Iterator
    • 541.Zigzag Iterator II
    • 423.Valid Parentheses
    • 488.Happy Number
    • 547.Intersection of Two Arrays
    • 548.Intersection of Two Arrays II
    • 627.Longest Palindrome
    • 638.Strings Homomorphism
    • 138.Subarray Sum
    • 647.Substring Anagrams
    • 171.Anagrams
    • 739. Daily Temperatures(M)
    • 496. Next Greater Element I (E)
    • 503. Next Greater Element II(M)
    • 316. Remove Duplicate Letters(M) & 1081. Smallest Subsequence of Distinct Characters
    • 239. Sliding Window Maximum (H)
    • 355. Design Twitter (M)
    • 895. Maximum Frequency Stack (H)
    • 20. Valid Parentheses (E)
    • 921. Minimum Add to Make Parentheses Valid (M)
    • 1541. Minimum Insertions to Balance a Parentheses String (M)
    • 32. Longest Valid Parentheses (H)
    • Basic Calculator (*)
      • 224. Basic Calculator
      • 227. Basic Calculator II (M)
    • 844. Backspace String Compare
    • 295. Find Median from Data Stream
    • 208. Implement Trie (Prefix Tree)
    • 461.Kth Smallest Numbers in Unsorted Array
    • 1152.Analyze user website visit pattern
    • 811. Subdomain Visit Count (M)
    • 71. Simplify Path (M)
    • 362. Design Hit Counter
  • 9.Dynamic Programming
    • Summary
      • 最优子结构 Optimal Sustructure
      • 子序列解题模板
      • 空间压缩
      • 背包问题
        • Untitled
      • 股票买卖问题
      • KMP
    • 109.Triangle
    • 110.Minimum Path Sum
    • 114.Unique Paths
    • 115.Unique Paths II
    • 70.Climbing Stairs
    • 272.Climbing StairsII
    • 116.Jump Game
    • 117.Jump Game II
    • 322.Coin Change
    • 518. Coin Change 2 ()
    • Backpack I~VI
      • LintCode 563.Backpack V (M)
    • Best Time to Buy and Sell Stock(*)
      • 121. Best Time to Buy and Sell Stock
      • 122. Best Time to Buy and Sell Stock II (M)
      • 123. Best Time to Buy and Sell Stock III (H)
      • 188. Best Time to Buy and Sell Stock IV (H)
      • 309. Best Time to Buy and Sell Stock with Cooldown (M)
      • 714. Best Time to Buy and Sell Stock with Transaction Fee (M)
    • 394.Coins in a line
    • 395.Coins in a Line II
    • 509. Fibonacci Number (E)
    • 931. Minimum Falling Path Sum (M)
    • 494. Target Sum (M)
    • 72. Edit Distance (H)
    • 300.Longest Increasing Subsequence
    • 1143. Longest Common Subsequence (M)
    • 718. Maximum Length of Repeated Subarray
    • 583. Delete Operation for Two Strings (M)
    • 712. Minimum ASCII Delete Sum for Two Strings(M)
    • 53. Maximum Subarray (E)
    • 516. Longest Palindromic Subsequence (M)
    • 1312. Minimum Insertion Steps to Make a String Palindrome (H)
    • 416. Partition Equal Subset Sum (M)
    • 64. Minimum Path Sum(M)
    • 651. 4 Keys Keyboards (M)
    • House Robber (*)
      • 198. House Robber (M)
      • 213. House Robbber II
      • 337. House Robber III (M)
    • Word Break (*)
      • 139.Word Break (M)
    • 140. Word Break II (H)
    • 828. Count Unique Characters of All Substrings of a Given String (H)
    • 174. Dungeon Game (H)
    • 1567. Maximum Length of Subarray With Positive Product (M)
  • 10. Graph
    • Introduction
      • 有向图的环检测
      • 拓扑排序
      • 二分图判定
      • Union-Find
      • 最小生成树(Minimum Spanning Tree)算法
        • KRUSKAL 最小生成树算法
        • Prim 最小生成树算法
      • Dijkstra 最短路径算法
      • BFS vs DFS
    • 797. All Paths From Source to Target (M)
    • 785. Is Graph Bipartite? (M)
    • 886. Possible Bipartition (M)
    • 130. Surrounded Regions (M)
    • 990. Satisfiability of Equality Equations (M)
    • 721. Accounts Merge (M)
    • 323. Number of Connected Components in an Undirected Graph (M)
    • 261. Graph Valid Tree
    • 1135. Connecting Cities With Minimum Cost
    • 1584. Min Cost to Connect All Points (M)
    • 277. Find the Celebrity (M)
    • 743. Network Delay Time (M)
    • 1631. Path With Minimum Effort (M)
    • 1514. Path with Maximum Probability (M)
    • 589.Connecting Graph
    • 🌟787. Cheapest Flights Within K Stops (M)
    • 2050. Parallel Courses III (H)
    • 1293. Shortest Path in a Grid with Obstacles Elimination (H)
    • 864. Shortest Path to Get All Keys (H)
    • 269. Alien Dictionary (H)
    • 1192. Critical Connections in a Network (H)
    • 529. Minesweeper (M)
  • 11.Math
    • Page 1
Powered by GitBook
On this page

Was this helpful?

  1. 10. Graph
  2. Introduction

Union-Find

https://labuladong.github.io/algo/2/19/37/

Previous二分图判定Next最小生成树(Minimum Spanning Tree)算法

Last updated 3 years ago

Was this helpful?

Union-Find 算法解决的是图的动态连通性问题

一、问题介绍

简单说,动态连通性其实可以抽象成给一幅图连线。比如下面这幅图,总共有 10 个节点,他们互不相连,分别用 0~9 标记:

现在我们的 Union-Find 算法主要需要实现这两个 API:

class UF {
    /* 将 p 和 q 连接 */
    public void union(int p, int q);
    /* 判断 p 和 q 是否连通 */
    public boolean connected(int p, int q);
    /* 返回图中有多少个连通分量 */
    public int count();
}

这里所说的「连通」是一种等价关系,也就是说具有如下三个性质:

1、自反性:节点 p 和 p 是连通的。

2、对称性:如果节点 p 和 q 连通,那么 q 和 p 也连通。

3、传递性:如果节点 p 和 q 连通,q 和 r 连通,那么 p 和 r 也连通。

比如说之前那幅图,0~9 任意两个不同的点都不连通,调用 connected 都会返回 false,连通分量为 10 个。

如果现在调用 union(0, 1),那么 0 和 1 被连通,连通分量降为 9 个。

再调用 union(1, 2),这时 0,1,2 都被连通,调用 connected(0, 2) 也会返回 true,连通分量变为 8 个。

判断这种「等价关系」非常实用,比如说编译器判断同一个变量的不同引用,比如社交网络中的朋友圈计算等等。

这样,你应该大概明白什么是动态连通性了,Union-Find 算法的关键就在于 union 和 connected 函数的效率。那么用什么模型来表示这幅图的连通状态呢?用什么数据结构来实现代码呢?

二、基本思路

注意我刚才把「模型」和具体的「数据结构」分开说,这么做是有原因的。因为我们使用森林(若干棵树)来表示图的动态连通性,用数组来具体实现这个森林。

怎么用森林来表示连通性呢?我们设定树的每个节点有一个指针指向其父节点,如果是根节点的话,这个指针指向自己。比如说刚才那幅 10 个节点的图,一开始的时候没有相互连通,就是这样:

class UF {
    // 记录连通分量
    private int count;
    // 节点 x 的节点是 parent[x]
    private int[] parent;

    /* 构造函数,n 为图的节点总数 */
    public UF(int n) {
        // 一开始互不连通
        this.count = n;
        // 父节点指针初始指向自己
        parent = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    /* 其他函数 */
}

如果某两个节点被连通,则让其中的(任意)一个节点的根节点接到另一个节点的根节点上:

public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP == rootQ)
        return;
    // 将两棵树合并为一棵
    parent[rootP] = rootQ;
    // parent[rootQ] = rootP 也一样
    count--; // 两个分量合二为一
}

/* 返回某个节点 x 的根节点 */
private int find(int x) {
    // 根节点的 parent[x] == x
    while (parent[x] != x)
        x = parent[x];
    return x;
}

/* 返回当前的连通分量个数 */
public int count() { 
    return count;
}

这样,如果节点 p 和 q 连通的话,它们一定拥有相同的根节点:

public boolean connected(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    return rootP == rootQ;
}

至此,Union-Find 算法就基本完成了。是不是很神奇?竟然可以这样使用数组来模拟出一个森林,如此巧妙的解决这个比较复杂的问题!

那么这个算法的复杂度是多少呢?我们发现,主要 API connected 和 union 中的复杂度都是 find 函数造成的,所以说它们的复杂度和 find 一样。

find 主要功能就是从某个节点向上遍历到树根,其时间复杂度就是树的高度。我们可能习惯性地认为树的高度就是 logN,但这并不一定。logN 的高度只存在于平衡二叉树,对于一般的树可能出现极端不平衡的情况,使得「树」几乎退化成「链表」,树的高度最坏情况下可能变成 N。

所以说上面这种解法,find , union , connected 的时间复杂度都是 O(N)。这个复杂度很不理想的,你想图论解决的都是诸如社交网络这样数据规模巨大的问题,对于 union 和 connected 的调用非常频繁,每次调用需要线性时间完全不可忍受。

问题的关键在于,如何想办法避免树的不平衡呢?只需要略施小计即可。

三、平衡性优化

我们要知道哪种情况下可能出现不平衡现象,关键在于 union 过程:

public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP == rootQ)
        return;
    // 将两棵树合并为一棵
    parent[rootP] = rootQ;
    // parent[rootQ] = rootP 也可以
    count--;

我们一开始就是简单粗暴的把 p 所在的树接到 q 所在的树的根节点下面,那么这里就可能出现「头重脚轻」的不平衡状况,比如下面这种局面:

长此以往,树可能生长得很不平衡。我们其实是希望,小一些的树接到大一些的树下面,这样就能避免头重脚轻,更平衡一些。解决方法是额外使用一个 size 数组,记录每棵树包含的节点数,我们不妨称为「重量」:

class UF {
    private int count;
    private int[] parent;
    // 新增一个数组记录树的“重量”
    private int[] size;

    public UF(int n) {
        this.count = n;
        parent = new int[n];
        // 最初每棵树只有一个节点
        // 重量应该初始化 1
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    /* 其他函数 */
}

比如说 size[3] = 5 表示,以节点 3 为根的那棵树,总共有 5 个节点。这样我们可以修改一下 union 方法:

public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP == rootQ)
        return;
    
    // 小树接到大树下面,较平衡
    if (size[rootP] > size[rootQ]) {
        parent[rootQ] = rootP;
        size[rootP] += size[rootQ];
    } else {
        parent[rootP] = rootQ;
        size[rootQ] += size[rootP];
    }
    count--;
}

这样,通过比较树的重量,就可以保证树的生长相对平衡,树的高度大致在 logN 这个数量级,极大提升执行效率。

此时,find , union , connected 的时间复杂度都下降为 O(logN),即便数据规模上亿,所需时间也非常少。

四、路径压缩

这步优化特别简单,所以非常巧妙。我们能不能进一步压缩每棵树的高度,使树高始终保持为常数?

这样 find 就能以 O(1) 的时间找到某一节点的根节点,相应的,connected 和 union 复杂度都下降为 O(1)。

要做到这一点,非常简单,只需要在 find 中加一行代码:

private int find(int x) {
    while (parent[x] != x) {
        // 进行路径压缩
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

这个操作有点匪夷所思,看个 GIF 就明白它的作用了(为清晰起见,这棵树比较极端):

  1. p[1]=2. p[2]=3, p[3]=4, p[4]=5, p[5]=5

  2. x=1: p[1] = p[p[2]]=3, x ->3; p[3] = p[p[4]]=5

  3. p[1] = 3. p[2]=3, p[3]=5, p[4]=5, p[5]=5;

可见,调用 find 函数每次向树根遍历的同时,顺手将树高缩短了,最终所有树高都不会超过 3(union 的时候树高可能达到 3)。

PS:读者可能会问,这个 GIF 图的find过程完成之后,树高恰好等于 3 了,但是如果更高的树,压缩后高度依然会大于 3 呀?不能这么想。这个 GIF 的情景是我编出来方便大家理解路径压缩的,但是实际中,每次find都会进行路径压缩,所以树本来就不可能增长到这么高,你的这种担心应该是多余的。

在这种情况下的完整代码:

class UF {
    // 连通分量个数
    private int count;
    // 存储一棵树
    private int[] parent;
    // 记录树的「重量」
    private int[] size;

    // n 为图中节点的个数
    public UF(int n) {
        this.count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    
    // 将节点 p 和节点 q 连通
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        
        // 小树接到大树下面,较平衡
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        // 两个连通分量合并成一个连通分量
        count--;
    }

    // 判断节点 p 和节点 q 是否连通
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    // 返回节点 x 的连通分量根节点
    private int find(int x) {
        while (parent[x] != x) {
            // 进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    // 返回图中的连通分量个数
    public int count() {
        return count;
    }
}

路径压缩的第二种写法是这样:

// 第二种路径压缩的 find 方法
public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

我一度认为这种递归写法和第一种迭代写法做的事情一样,但实际上是我大意了,有读者指出这种写法进行路径压缩的效率是高于上一种解法的。

这个递归过程有点不好理解,你可以自己手画一下递归过程。我把这个函数做的事情翻译成迭代形式,方面你理解它进行路径压缩的原理:

// 这段迭代代码方便你理解递归代码所做的事情
public int find(int x) {
    // 先找到根节点
    int root = x;
    while (parent[root] != root) {
        root = parent[root];
    }
    // 然后把 x 到根节点之间的所有节点直接接到根节点下面
    int old_parent = parent[x];
    while (x != root) {
        parent[x] = root;
        x = old_parent;
        old_parent = parent[old_parent];
    }
    return root;
}

这种路径压缩的效果如下:

比起第一种路径压缩,显然这种方法压缩得更彻底,直接把一整条树枝压平,一点意外都没有,所以从效率的角度来说,推荐你使用这种路径压缩算法。

另外,如果路径压缩技巧将树高保持为常数了,那么 size 数组的平衡优化就不是特别必要了。

所以你一般看到的 Union Find 算法应该是如下实现:

class UF {
    // 连通分量个数
    private int count;
    // 存储每个节点的父节点
    private int[] parent;

    // n 为图中节点的个数
    public UF(int n) {
        this.count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    // 将节点 p 和节点 q 连通
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        
        if (rootP == rootQ)
            return;
        
        parent[rootQ] = rootP;
        // 两个连通分量合并成一个连通分量
        count--;
    }

    // 判断节点 p 和节点 q 是否连通
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 返回图中的连通分量个数
    public int count() {
        return count;
    }
}

五、最后总结

Union-Find 算法的复杂度可以这样分析:构造函数初始化数据结构需要 O(N) 的时间和空间复杂度;连通两个节点 union、判断两个节点的连通性 connected、计算连通分量 count 所需的时间复杂度均为 O(1)。

到这里,相信你已经掌握了 Union-Find 算法的核心逻辑,总结一下我们优化算法的过程:

1、用 parent 数组记录每个节点的父节点,相当于指向父节点的指针,所以 parent 数组内实际存储着一个森林(若干棵多叉树)。

2、用 size 数组记录着每棵树的重量,目的是让 union 后树依然拥有平衡性,保证各个 API 时间复杂度为 O(logN),而不会退化成链表影响操作效率。

3、在 find 函数中进行路径压缩,保证任意树的高度保持在常数,使得各个 API 时间复杂度为 O(1)。使用了路径压缩之后,可以不使用 size 数组的平衡优化。

三、简单总结

使用 Union-Find 算法,主要是如何把原问题转化成图的动态连通性问题。对于算式合法性问题,可以直接利用等价关系,对于棋盘包围问题,则是利用一个虚拟节点,营造出动态连通特性。

另外,将二维数组映射到一维数组,利用方向数组 d 来简化代码量,都是在写算法时常用的一些小技巧,如果没见过可以注意一下。

很多更复杂的 DFS 算法问题,都可以利用 Union-Find 算法更漂亮的解决。LeetCode 上 Union-Find 相关的问题也就二十多道,有兴趣的读者可以去做一做。

(leetcode 130, 990)

Union-Find算法应用