Disjoint Set / Union-Find

Question 1

What is a disjoint set?

Answer 1

A collection of sets where no element appears in more than one set.

Question 2

What is the union-find data structure?

Answer 2

A data structure that tracks a partition of elements into disjoint sets.

Question 3

What are the main operations of disjoint set?

Answer 3

Find and Union.

Question 4

What does the find operation do?

Answer 4

Determines the representative (or root) of the set containing an element.

Question 5

What does the union operation do?

Answer 5

Merges two disjoint sets into a single set.

Question 6

What is path compression?

Answer 6

An optimization that flattens the structure of the tree to speed up future find operations.

Question 7

What is union by rank?

Answer 7

An optimization that attaches the shorter tree under the root of the taller tree.

Question 8

What is the time complexity of find and union with optimizations?

Answer 8

Nearly O(1), specifically O(α(n)), where α is the inverse Ackermann function.

Question 9

What is the inverse Ackermann function?

Answer 9

A very slowly growing function used in the analysis of disjoint set operations.

Question 10

What is a representative element in a disjoint set?

Answer 10

The element used to identify the set, usually the root of the tree.

Question 11

How is a disjoint set represented?

Answer 11

As a forest of trees using parent pointers.

Question 12

What is the parent array in union-find?

Answer 12

An array where each index points to its parent, used to represent sets.

Question 13

What is the rank array used for?

Answer 13

To keep track of the height or depth of trees in union-find.

Question 14

What is the initial value of each element in the parent array?

Answer 14

Each element is initially its own parent.

Question 15

What is the use of union-find in Kruskal’s algorithm?

Answer 15

To detect cycles while building a minimum spanning tree.

Question 16

How do you check if two elements are in the same set?

Answer 16

Compare their roots using the find operation.

Question 17

What is the space complexity of disjoint set with n elements?

Answer 17

O(n)

Question 18

How is path compression implemented?

Answer 18

By making each node on the path point directly to the root.

Question 19

What is union by size?

Answer 19

An optimization where the smaller set is attached to the larger one.

Question 20

Which is better: union by rank or union by size?

Answer 20

Both are efficient; union by rank is more commonly used.

Question 21

Can union-find be used in dynamic connectivity problems?

Answer 21

Yes, to maintain and query components efficiently.

Question 22

What is a real-world use case of disjoint sets?

Answer 22

Tracking connected components in a network.

Question 23

What is the role of union-find in maze generation?

Answer 23

To ensure that adding a passage does not create a cycle.

Question 24

What is the role of disjoint sets in clustering?

Answer 24

To group similar data points during algorithms like k-clustering.

Question 25

What happens if you union elements already in the same set?

Answer 25

Nothing changes; they are already connected.

Question 26

What is the amortized time complexity of union-find operations?

Answer 26

O(α(n)) per operation.

Question 27

How do you initialize a disjoint set with n elements?

Answer 27

Create a parent array with each index set to itself.

Question 28

What happens during repeated find calls without path compression?

Answer 28

The depth of the tree can grow, making find slower.

Question 29

How do disjoint sets help in detecting cycles?

Answer 29

By checking if two nodes are already connected before uniting them.

Question 30

What is connected component identification?

Answer 30

Using disjoint sets to find groups of connected elements.

Question 31

What is a flat tree in union-find?

Answer 31

A tree where each node points directly to the root.

Question 32

Can union-find be used in dynamic graph problems?

Answer 32

Yes, especially for offline queries and connectivity.

Question 33

What is a drawback of naive union without rank?

Answer 33

It can lead to deep trees and slow find operations.

Question 34

What is the purpose of the find operation returning the root?

Answer 34

To identify the set to which an element belongs.

Question 35

What is a common mistake in implementing union-find?

Answer 35

Forgetting to apply path compression in find.

Question 36

What are the advantages of union-find over DFS/BFS for connectivity?

Answer 36

Faster for multiple offline queries.

Question 37

Can union-find handle merge and split operations?

Answer 37

It efficiently handles merges but not splits.

Question 38

Is union-find suitable for dynamic addition/removal of elements?

Answer 38

Not for removals; it is static for most use cases.

Question 39

How is union-find used in image processing?

Answer 39

To group pixels into regions or connected components.

Question 40

What is a supernode in disjoint sets?

Answer 40

The root of a set that represents the entire group.

Question 41

What is the total time for m operations on n elements?

Answer 41

O(m * α(n))

Question 42

How do you implement disjoint sets in code?

Answer 42

Use arrays for parent and rank, with recursive or iterative find.

Question 43

Can disjoint sets detect equivalence classes?

Answer 43

Yes, they group items with the same relation.

Question 44

Why is the union-find algorithm efficient?

Answer 44

Because of path compression and union by rank.

Question 45

What is the use of disjoint sets in social networks?

Answer 45

To find friend groups or communities.

Question 46

What is the initialization cost of disjoint sets?

Answer 46

O(n), for setting each element as its own parent.