Data Structures u0026 Algorithms: Disjoint Set Union and Applications Quiz

Test your knowledge of Disjoint Set Union (Union-Find) data structure, its algorithms, and core applications such as cycle detection, Kruskal’s algorithm, and connected component analysis.

1. Detecting Cycles Efficiently

   Given an undirected graph with N nodes and M edges, which approach using Disjoint Set Union (DSU) most effectively detects cycles during the addition of each edge?

   1. Union nodes only, then count degrees
   2. Use BFS for every insertion
   3. Check if two nodes are in the same set before union
   4. Merge all sets at once before processing
   5. Sort edges by weight before union

2. Optimized DSU Operations

   What is the amortized time complexity per operation when both path compression and union by rank are used in a DSU implementation with N elements?

   1. O(N)
   2. O(log N)
   3. O(log log N)
   4. O(α(N))
   5. O(1)

3. Kruskal’s Algorithm and DSU

   In Kruskal's Minimum Spanning Tree algorithm, how does DSU prevent cycles during the construction of the spanning tree?

   1. It removes the heaviest edge each time
   2. It prioritizes degree of nodes
   3. It ensures only edges connecting different sets are added
   4. It checks all paths from source to destination
   5. It only connects nodes of the same set

4. Path Compression Functionality

   Which operation in DSU directly contributes to flattening the tree structure for faster subsequent searches: union by rank or path compression?

   1. Find with parent reset
   2. Heapify
   3. Unio by rnak
   4. Path compresion
   5. Union with size

5. Connected Component Counting

   Given a graph of 10 nodes and a set of edges, how would you utilize DSU to compute the total number of connected components after all unions?

   1. Divide total edges by 2
   2. Use BFS from each node
   3. Count unique leaders after all finds
   4. Sum degrees of all nodes
   5. Multiply number of unions by 2

6. Union by Rank vs. Union by Size

   Suppose you implement union by size in one DSU and union by rank in another; what practical difference might emerge regarding the resulting tree heights?

   1. Union by rank merges smaller sets into larger regardless of rank
   2. There is no difference at all
   3. Union by size always creates linear trees
   4. Trees in union by size may be taller
   5. Union by rank guarantees shorter trees

7. DSU in Dynamic Connectivity

   When processing a sequence of queries, each asking whether two nodes are in the same connected component in a dynamic graph, why is DSU preferred over adjacency lists or matrices?

   1. DSU provides faster updates and queries for large graphs
   2. Adjacency lists cannot track previous connections
   3. Adjacency matrices can only be used for weighted graphs
   4. DSU has lower memory overhead for all operations
   5. DSU can insert self-loops directly

8. DSU for Edge Removal

   What is a primary limitation of classic DSU regarding edge removals in a dynamically changing undirected graph?

   1. DSU only works for directed graphs
   2. Removing an edge automatically merges sets
   3. DSU cannot efficiently remove connections once added
   4. DSU doubles the memory needed after removal
   5. Edge removals make path compression less effective

9. Generalized Applications

   Which of the following problems cannot be efficiently solved using a standard DSU data structure?

   1. Minimum spanning tree computation
   2. Connected component labeling
   3. Connectivity after arbitrary edge deletions
   4. Dynamic connectivity queries
   5. Finding cycles in an undirected graph

10. Advanced DSU Extension

    Suppose you need to support both union and query for the minimum value within each set; what DSU extension would allow you to maintain this property efficiently?

    1. Use degree of each node as set representative
    2. Apply path compression aggressively after every query
    3. Store and update minimum value at the root during union
    4. Recompute minimums globally after each update
    5. Sort sets after every union operation