24. Disjoint Set Union (DSU / Union-Find): Redundant Connection & Number of Connected Components • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep › 24. Disjoint Set Union (DSU / Union-Find): Redundant Connection & Number of Connected Components

50 mins

← Prev Next →

Course Syllabus

Module 1: Big-O Asymptotics, Arrays & Sliding Window

01. Time & Space Complexity Masterclass: Big-O, Big-Theta, Big-Omega & Amortized Analysis 02. Arrays & Hashing: Two Sum, Contains Duplicate & Valid Anagram (Hash Table Lookups) 03. Prefix Sum & Kadane's Algorithm (Maximum Subarray Problem in O(N)) 04. Sliding Window Pattern: Fixed vs Dynamic Windows (Best Time to Buy/Sell Stock)

Module 2: Two Pointers & Binary Search Systems

05. Two Pointers Pattern: Valid Palindrome, 3Sum & Container With Most Water 06. Binary Search Foundations: Search in Rotated Sorted Array & Find Minimum 07. Binary Search on Answer Space: Koko Eating Bananas & Capacity to Ship Packages

Module 3: Linked Lists & Fast-Slow Pointer Patterns

08. Singly vs Doubly Linked Lists & In-Place Pointer Manipulation (Reverse Linked List) 09. Fast & Slow Pointer (Floyd's Cycle Detection): Linked List Cycle & Middle Node 10. Merging & Reordering: Merge Two Sorted Lists, Reorder List & Remove Nth Node

Module 4: Stacks, Queues & Monotonic Stack Architecture

11. Stack Fundamentals: Valid Parentheses & Min Stack in O(1) Time 12. Monotonic Stack Pattern: Daily Temperatures & Next Greater Element 13. Hard Stack Coding: Largest Rectangle in Histogram & Trapping Rain Water

Module 5: Trees, Binary Search Trees & DFS/BFS Traversals

14. Binary Tree Architecture: Max Depth, Same Tree & Invert Binary Tree 15. BFS Level-Order Traversal & Binary Tree Right Side View 16. Binary Search Tree (BST) Properties: Validate BST & Lowest Common Ancestor (LCA) 17. Tree Path Sums & Serialize / Deserialize Binary Tree (Hard)

Module 6: Heaps, Priority Queues & Top-K Problems

18. Min Heap & Max Heap Internals: Array Representation & Heapify in O(N) 19. Top-K Elements Pattern: Kth Largest Element in an Array & Top K Frequent Elements 20. Two-Heap Pattern: Find Median from Data Stream (Hard)

Module 7: Graphs, Topological Sort & Shortest Paths (Dijkstra)

21. Graph Representations (Adjacency Matrix vs List) & DFS/BFS Traversal 22. Matrix Graph Traversal: Number of Islands, Max Area of Island & Clone Graph 23. Topological Sort (Kahn's Algorithm): Course Schedule I & II (Cycle Detection) 24. Disjoint Set Union (DSU / Union-Find): Redundant Connection & Number of Connected Components

Module 8: Dynamic Programming, Backtracking & Bit Manipulation

25. Backtracking Pattern: Subsets, Permutations, Combination Sum & Word Search 26. 1D Dynamic Programming: Climbing Stairs, House Robber & Coin Change 27. Longest Increasing Subsequence (LIS): O(N^2) DP vs O(N log N) Patience Sort 28. 2D Dynamic Programming: Unique Paths, Longest Common Subsequence (LCS) & Edit Distance 29. 0/1 Knapsack Pattern & Partition Equal Subset Sum 30. Bit Manipulation Tricks: Number of 1 Bits (Hamming Weight), Counting Bits & Missing Number

Interactive Lesson Studio

# 24. Disjoint Set Union (DSU / Union-Find): Redundant Connection & Number of Connected Components

> DSA Blind 75 Notes by Rishabh - Topic 24

---

### 1. Disjoint Set Union (DSU / Union-Find) Architecture 🤝

DSU dynamic connectivity track karne ka world-class data structure hai with **near $O(1)$ operations ($\alpha(N)$ - Inverse Ackermann Function)**:
1. **`find(x)`:** Node $x$ ke set ka representative leader (Root) dhoondhna with **Path Compression**.
2. **`union(x, y)`:** Do sets ko merge karna with **Union by Rank/Size**.

```python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [1] * (n + 1)
        
    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i]) # ⚡ Path Compression!
        return self.parent[i]
        
    def union(self, i, j) -> bool:
        root_i, root_j = self.find(i), self.find(j)
        if root_i == root_j:
            return False # 💥 Already connected -> Cycle / Redundant edge!
            
        # Union by Rank:
        if self.rank[root_i] < self.rank[root_j]:
            self.parent[root_i] = root_j
        elif self.rank[root_i] > self.rank[root_j]:
            self.parent[root_j] = root_i
        else:
            self.parent[root_j] = root_i
            self.rank[root_i] += 1
        return True
```

---

### 2. LeetCode #684: Redundant Connection ($O(N \cdot \alpha(N))$)

*Problem:* Tree me dali gayi wo extra edge dhoondho jo cycle create kar rahi hai.

```python
def findRedundantConnection(edges: list[list[int]]) -> list[int]:
    dsu = DSU(len(edges))
    for u, v in edges:
        if not dsu.union(u, v):
            return [u, v] # ⚡ Found cycle creating redundant edge!
    return []
```

---

### 3. Master Comparison Matrix

---

### 4. Interview Ke 3 Sawal Is Topic Se

1. **Kruskal's Minimum Spanning Tree (MST) me DSU kaise use hota hai?** -> Saare edges ko weight ke hisab se sort karo aur DSU union chala kar cycle create karne wali edges ko ignore karo ($O(E \log E)$).
2. **Number of Connected Components in Undirected Graph (LeetCode #323) DSU se kaise count hota hai?** -> Initial components count $N$ initialize karo aur har successful `union()` par `components -= 1` karo.
3. **Inverse Ackermann function $\alpha(N)$ ki practical value kitni hoti hai?** -> Universe ke kisi bhi number ($N = 10^{80}$) ke liye $\alpha(N) < 5$ hoti hai, isliye ise practically constant $O(1)$ maana jata hai.

---
**Next Topic:** 25. Backtracking Pattern: Subsets, Permutations, Combination Sum & Word Search

Loading lesson content...

JavaScript

Full IDE

Live Execution Terminal

Click "Execute Live" to run code.
                

Lesson Mastery AI Quiz

AI Doubt Solver

CERTIFICATE OF COMPLETION

Rishabh Gehlot

PHP 8+ & Laravel 11 Master Track