Union-Find - Connected Components and Network Detection

Public lesson preview

Learn the Union-Find (disjoint set) data structure with path compression and union by rank. Solve connectivity, MST, and graph component problems efficiently.

Learning objectives

By the end of this lesson, you will understand:

• ✓The Connectivity Problem
• ✓Naive Approach - Quick Find
• ✓The Union-Find Data Structure
• ✓Find with Path Compression
• ✓Union by Rank

Lesson outline

1. The Connectivity Problem
2. Naive Approach - Quick Find
3. The Union-Find Data Structure
4. Find with Path Compression
5. Union by Rank
6. Kruskal's MST Algorithm
7. Classic Problems
8. Number of Connected Components
9. Accounts Merge (LeetCode 721)
10. Redundant Connection (LeetCode 684)
11. When to Choose Union-Find vs BFS/DFS
12. 📚 Further Reading