Learn
Exam

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.

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 two operations:

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

Disjoint sets are typically represented using trees with root nodes. For example:

Initially, each vertex (1 to 7) is in its own set, where the set number matches the vertex number:

Performing Union 2, 5 merges the sets containing vertices 2 and 5. The set number is updated to the lower number:

Performing Union 4, 7 similarly updates the set numbers:

The Find operation determines the set number. For example, Find 7 returns 4:

Performing Union 1, 7 merges the sets containing 1 and 7, resulting in the following structure:

Similarly, performing Union 5, 3 updates the set numbers:

After these operations, vertex 3 is in the set represented by 2:

Finally, performing Union 5, 7 merges sets containing 5 and 7 into the set represented by 1:

Afterward, vertex 3 is confirmed to be in the set represented by 1:

Union-Find optimizations such as Union By Rank and Path Compression reduce query time complexity to nearly constant time. Without optimization, each query requires begin:math:textbegin:math:textO(N)end:math:textend:math:text time, but with optimizations, the time complexity becomes begin:math:textbegin:math:textO(\alpha(N))end:math:textend:math:text, where begin:math:textbegin:math:text\alpha(N)end:math:textend:math:text is the inverse Ackermann function.

Constraints

  • n is the number of vertices (1 ≤ n ≤ 10,000).
  • queries contains up to 10,000 elements:
    • [-1, x, y]: Merge vertices x and y.
    • [-2, x, y]: Check if x and y belong to the same set and return true or 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,3,4],[-2,4,1]] [false, true]
2 9 [[-1,2,7],[-2,2,7],[-2,2,7],[-1,6,9],[-1,6,8]] [true, true, true]
3 5 [[-1,3,5],[-2,5,1],[-1,1,5],[-1,3,5],[-1,2,5]] [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 [-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}