Learn
Exam

Optimized Union-Find Algorithm

Difficulty
INTERMEDIATE

Problem

Given the number of vertices n and query information queries, write a solution function to process queries based on their types and return the results in order.

There are two types of queries:

  • [-1, x, y] - Union Query:
    Merge vertices x and y into the same set.
  • [-2, x, y] - Find Query:
    Return true if vertices x and y belong to the same set; otherwise, return false.

x and y are distinct natural numbers between 1 and n.

Concept Explanation

The Union-Find Algorithm is a method to efficiently represent and manipulate disjoint sets. It supports the following operations:

  • Union: Merge two disjoint sets into one.
  • Find: Determine which set an element belongs to.

The basic functionality of the Union-Find algorithm is detailed in the "[Representative Type] Union-Find Algorithm".

The algorithm can be significantly optimized by applying two strategies: Union By Rank/Size and Path Compression.

Union By Rank/Size

When merging two disjoint sets, this strategy attaches the smaller tree to the larger tree to minimize the overall height of the resulting tree.

For example, consider two disjoint trees and a Union operation between vertices 6 and 10:

There are two possible ways to merge the trees:

The second method is more optimal for future queries because it minimizes the height of the tree.

By using this strategy, the maximum tree height is guaranteed to be begin:math:textbegin:math:text \log_2(N)+1 end:math:textend:math:text, and the time complexity of Union/Find operations becomes begin:math:textbegin:math:text O(\log_2(N)) end:math:textend:math:text.

Path Compression

During the Find operation, the parent of each node in the path is updated to point directly to the root node, flattening the tree structure and reducing the depth for future queries.

For example, consider the following tree before performing Find on vertex 10:

The Find operation determines that the root node is vertex 1. After applying Path Compression, all nodes in the path (4, 6, and 10) directly point to the root node:

After compression:

By flattening the tree, the depth of recursive calls during future Find queries is reduced.

Constraints

  • n is the number of vertices (1 ≤ n ≤ 100,000).
  • Each vertex has a unique ID from 1 to n.
  • queries contains up to 100,000 queries, each in one of the following formats:
    • [-1, x, y]: Merge vertices x and y.
    • [-2, x, y]: Return true if x and y are in the same set; otherwise, return false.

x, y are distinct natural numbers between 1 and n.

Test Cases

Test Case Number n queries return
1 5 [[-1,3,5],[-1,4,1],[-2,4,3],[-2,4,1]] [false,true]
2 9 [[-1,2,7],[-2,2,7],[-2,2,7],[-1,6,9],[-1,6,8],[-1,9,2],[-1,2,3],[-2,3,8],[-1,9,7],[-2,6,9]] [true,true,true,true]
3 5 [[-1,3,5],[-2,5,1],[-1,1,5],[-1,3,5],[-1,2,5],[-1,1,2],[-2,5,4]] [false,false]

Explanation for Test Case 1

  • Query [-1,3,5]: {1}, {2}, {3,5}, {4}
  • Query [-1,4,1]: {1,4}, {2}, {3,5}
  • Query [-2,3,4]: false
  • Query [-2,4,1]: true

Explanation for Test Case 2

  • Query [-1,2,7]: {1}, {2,7}, {3}, {4}, {5}, {6}, {8}, {9}
  • Query [-2,2,7]: true
  • Query [-2,2,7]: true
  • Query [-1,6,9]: {1}, {2,7}, {3}, {4}, {5}, {6,9}, {8}
  • Query [-1,6,8]: {1}, {2,7}, {3}, {4}, {5}, {6,8,9}

Explanation for Test Case 3

  • Query [-1,3,5]: {1}, {2}, {3,5}, {4}
  • Query [-2,5,1]: false
  • Query [-1,1,5]: {1,3,5}, {2}, {4}
  • Query [-1,3,5]: {1,3,5}, {2}, {4}
  • Query [-1,2,5]: {1,2,3,5}, {4}
  • Query [-1,1,2]: {1,2,3,5}, {4}