Union find

Question 1

What is the definition of Union Find?

Answer 1

Tracks disjoint sets with union and find operations.

Question 2

When is Union Find used?

Answer 2

Used for connected components and cycle detection.

Question 3

What is an example use case for Union Find?

Answer 3

Number of Provinces.

Question 4

What are the key steps in Union Find?

Answer 4

1. Initialize parent array for each node.
2. Find: Get root with path compression.
3. Union: Merge sets by rank.

Question 5

How does Union Find apply to Number of Provinces?

Answer 5

Count connected provinces in graph by unioning connected cities and counting distinct roots.

Question 6

What is the complexity of Union Find?

Answer 6

Time: O(α(n)) per operation, Space: O(n).

Question 7

What are some gotchas with Union Find?

Answer 7

Disconnected graph and self-loops.

Question 8

Provide a code example for Union Find.

Answer 8

```python
from typing import List
class UnionFind:
def __init__(self, size: int) -> None:
self.parent = list(range(size))
self.rank = [0] * size
self.count = size
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x: int, y: int) -> None:
px, py = self.find(x), self.find(y)
if px == py:
return
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
self.count -= 1

def find_circle_num(is_connected: List[List[int]]) -> int:
n = len(is_connected)
uf = UnionFind(n)
for i in range(n):
for j in range(i + 1, n):
if is_connected[i][j]:
uf.union(i, j)
return uf.count
~~~

Question 9

What visual aids can be used for Union Find?

Answer 9

Sketch union operations on paper.