Disjoint set (Union-Find) in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the purpose of Disjoint Set

What is the primary purpose of a Disjoint Set (Union-Find) data structure?

A To sort elements in ascending order using divide and conquer

B To implement a priority queue with fast insertion and extraction

C To store key-value pairs for fast lookup

D To efficiently manage a collection of non-overlapping sets and quickly determine if two elements belong to the same set

💡 Hint

Think about grouping elements and checking their group membership efficiently.

The Disjoint Set data structure is designed to keep track of elements partitioned into disjoint sets and supports two main operations: finding which set an element belongs to and uniting two sets. It is not used for sorting, key-value storage, or priority queues.

📋 Factual

intermediate

Time complexity of Union-Find operations

What is the amortized time complexity of the find and union operations in a Disjoint Set with path compression and union by rank/size?

A O(1) amortized

B O(log n) amortized

C O(α(n)) amortized, where α is the inverse Ackermann function

D O(n) amortized

💡 Hint

The inverse Ackermann function grows extremely slowly and is practically constant for all reasonable input sizes.

With path compression and union by rank or size, both find and union operations run in nearly constant time, specifically O(α(n)), where α(n) is the inverse Ackermann function, which grows very slowly and can be considered almost constant for all practical input sizes.

🔍 Analysis

advanced

Result of union operations sequence

Given a Disjoint Set with elements {1, 2, 3, 4, 5} initially all separate, what is the number of distinct sets after performing these operations in order?

union(1, 2)
union(3, 4)
union(2, 3)
union(5, 1)

A 2

B 1

C 3

D 4

💡 Hint

Track how sets merge step-by-step.

Initially, there are 5 sets: {1}, {2}, {3}, {4}, {5}.
After union(1, 2): {1,2}, {3}, {4}, {5}
After union(3, 4): {1,2}, {3,4}, {5}
After union(2, 3): {1,2,3,4}, {5}
After union(5, 1): {1,2,3,4,5}
Only one set remains.

❓ Comparison

advanced

Difference between union by rank and union by size

Which statement correctly describes the difference between union by rank and union by size in Disjoint Set implementations?

A Union by rank attaches the tree with smaller height under the root of the tree with larger height, while union by size attaches the tree with fewer nodes under the root of the tree with more nodes

B Union by rank attaches the tree with fewer nodes under the root of the tree with more nodes, while union by size attaches the tree with smaller height under the root of the tree with larger height

C Union by rank always results in taller trees than union by size

D Union by rank and union by size are identical and interchangeable without any difference

💡 Hint

Consider what 'rank' and 'size' represent in the context of trees.

Union by rank uses the height (or an upper bound on height) of the tree to decide which root becomes the parent, attaching the shorter tree under the taller one. Union by size uses the number of nodes in the tree to decide, attaching the smaller tree under the larger one. They are similar but use different criteria.

❓ Reasoning

expert

Detecting cycle in an undirected graph using Disjoint Set

Consider an undirected graph with edges added one by one. How can a Disjoint Set be used to detect if adding a new edge creates a cycle?

A Check if the two vertices of the new edge belong to the same set; if yes, adding the edge creates a cycle

B Check if the two vertices of the new edge belong to different sets; if yes, adding the edge creates a cycle

C Use Disjoint Set to count the total number of edges and vertices to detect cycles

D Always add the edge without any checks; cycles cannot be detected using Disjoint Set

💡 Hint

Think about what it means if two vertices are already connected before adding an edge.

If the two vertices of the new edge are already in the same set, it means they are connected by some path. Adding the edge would create a cycle. If they are in different sets, the edge connects two separate components and does not form a cycle.