What is Union-Find used for?

It helps group elements and determine whether two elements are in the same set.

What is path compression in Union-Find?

Path compression flattens the tree during 'find' to optimize future queries.

What is Union-Find or Disjoint Set Data Structure | FullStackPrep.Dev

💡 Concept Name

Union-Find / Disjoint Set – A data structure used to efficiently group elements into disjoint sets and quickly determine whether elements belong to the same set.

📘 Quick Intro

Union-Find is primarily used in algorithms that deal with dynamic connectivity like Kruskal’s Minimum Spanning Tree or detecting cycles in graphs. It consists of two main operations: find and union.

🧠 Analogy / Short Story

Imagine tracking social groups. When two people meet and become part of the same friend group, we merge their groups. Later, we may ask: "Are these two people in the same friend circle?" That’s Union-Find!

🔧 Technical Explanation

🔍 Find: Returns the representative (parent) of the set an element belongs to.
🔗 Union: Merges two sets by linking their representatives.
🪄 Path Compression: Speeds up future queries by flattening the tree structure during find operations.
📊 Union by Rank: Keeps the tree shallow by attaching the smaller tree under the taller one.
⏱️ Time Complexity: Near constant O(α(n)) using both path compression and union by rank.

🎯 Purpose & Use Case

✅ Cycle detection in graphs
✅ Kruskal’s algorithm for MST
✅ Dynamic connectivity queries
✅ Network connectivity checks

💻 Real Code Example

class UnionFind
{
    private int[] parent;
    private int[] rank;

    public UnionFind(int size)
    {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++)
            parent[i] = i;
    }

    public int Find(int x)
    {
        if (parent[x] != x)
            parent[x] = Find(parent[x]); // Path Compression
        return parent[x];
    }

    public void Union(int x, int y)
    {
        int xRoot = Find(x);
        int yRoot = Find(y);
        if (xRoot == yRoot) return;

        if (rank[xRoot] < rank[yRoot])
            parent[xRoot] = yRoot;
        else if (rank[xRoot] > rank[yRoot])
            parent[yRoot] = xRoot;
        else
        {
            parent[yRoot] = xRoot;
            rank[xRoot]++;
        }
    }
}

❓ Interview Q&A

Q1: What is the Union-Find or Disjoint Set Union (DSU) data structure?
A: A data structure that keeps track of elements partitioned into disjoint sets and supports union and find operations efficiently.

Q2: What are the two main operations in DSU?
A: Find (to identify which set an element belongs to) and Union (to merge two sets).

Q3: How does the Find operation work?
A: It returns the representative or parent of the set containing the element.

Q4: What is path compression in DSU?
A: An optimization technique that flattens the structure of the tree during Find operations to speed up future queries.

Q5: What is union by rank or size?
A: An optimization that always attaches the smaller tree under the root of the larger tree during union.

Q6: What is the time complexity of DSU operations with optimizations?
A: Nearly O(1) amortized, often described as inverse Ackermann function, practically constant.

Q7: What are common use cases of DSU?
A: Cycle detection in graphs, Kruskal’s MST algorithm, network connectivity.

Q8: How is DSU represented internally?
A: Usually by an array where each element points to its parent.

Q9: Can DSU handle dynamic insertion of new elements?
A: Typically no; DSU is static but can be adapted with dynamic techniques.

Q10: Why is DSU preferred over other methods for connectivity problems?
A: Because it provides efficient union and find operations with near constant time.

📝 MCQs

Q1. What does DSU stand for?

Disjoint Set Union
Direct Set Union
Disjoint Sorted Union
Dynamic Set Union

Q2. What are the main operations in DSU?

Insert and Delete
Find and Union
Search and Sort
Add and Remove

Q3. What does Find operation return?

Element value
Set representative
Set size
Root node data

Q4. What is path compression?

Sorting technique
Optimization to flatten trees
Union technique
Search method

Q5. What is union by rank?

Attach larger tree to smaller
Attach smaller tree to larger
Merge randomly
No merging

Q6. What is the amortized time complexity of DSU operations?

O(n)
O(log n)
Nearly O(1)
O(n log n)

Q7. Which algorithm commonly uses DSU?

Dijkstra's
Kruskal's MST
Prim's MST
Bellman-Ford

Q8. How is DSU internally represented?

Linked list
Parent array
Stack
Queue

Q9. Can DSU handle dynamic insertion?

Yes
Generally no
Only in trees
Only in graphs

Q10. Why is DSU efficient for connectivity problems?

Slow union and find
Fast union and find
Uses hashing
Uses sorting

💡 Bonus Insight

Union-Find is not just useful in graphs. It is also used in image processing (for connected components), clustering algorithms, and even in puzzles like Sudoku to ensure group constraints.

📄 PDF Download

Need a handy summary for your notes? Download this topic as a PDF!

📄 PDF Download Coming Soon

What is Union-Find or Disjoint Set Data Structure