Union-Find (Disjoint Set Union - DSU) — Graph Traversal Patterns (DFS & BFS)

The Union-Find (Disjoint Set Union - DSU) pattern applies when you need the Union-Find (Disjoint Set Union - DSU) technique within the Graph Traversal Patterns (DFS & BFS) pattern. Its time complexity is O(α(n)) per operation and space complexity O(n). It is used in 10 problems on Thita, including Accounts Merge, Graph Valid Tree and Largest Component Size by Common Factor. Common variations are Graph DFS - Cycle Detection (Directed Graph) and Deep Copy / Cloning.

Master Union-Find data structure with path compression and union by rank for connectivity problems.

Union-Find (Disjoint Set Union - DSU) is one of the 12 subpatterns of the Graph Traversal Patterns (DFS & BFS) pattern, which covers dFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST. The whole pattern is about 5 hours of study. This subpattern is a depth topic for once the core techniques are automatic.

What Union-Find (Disjoint Set Union - DSU) covers

Master graph algorithms including DFS/BFS traversal, topological sort, shortest paths (Dijkstra, Bellman-Ford), Union-Find, and advanced graph concepts. Problems in this subpattern are usually searched for as Union-Find, disjoint set, DSU, path compression, union by rank, redundant connection.

How to practise Union-Find (Disjoint Set Union - DSU) on Thita.ai

Read the theory for Union-Find (Disjoint Set Union - DSU), then work the problems attached to it in the browser editor. Your solution runs against the problem's test cases, and the AI coach offers a hint about the technique you are missing rather than a finished solution. Progress is tracked per subpattern, so the Graph Traversal Patterns (DFS & BFS) tracker shows this one as covered once you have solved its problems.

Other subpatterns in Graph Traversal Patterns (DFS & BFS)

• Graph DFS - Connected Components / Island Counting — Use DFS to find connected components and count islands in grids. Flood fill and province counting problems.
• Graph BFS - Connected Components / Island Counting — Use BFS for shortest path in unweighted graphs. Solve word ladder, rotting oranges, and matrix problems.
• Graph BFS - Topological Sort (Kahn's Algorithm) — Master topological sorting using Kahn's BFS algorithm. Solve course schedule and build order problems.
• Graph DFS - Cycle Detection (Directed Graph) — Detect cycles in directed graphs using DFS with coloring (white, gray, black) approach.
• Deep Copy / Cloning — Learn to deep copy and clone graph structures using DFS/BFS with visited mapping.
• Shortest Path (Dijkstra's Algorithm) — Master Dijkstra's algorithm for finding shortest paths in weighted graphs with non-negative edges.
• Shortest Path (Bellman-Ford / BFS+K) — Find shortest paths with constraints using Bellman-Ford algorithm and BFS with limited stops.
• Bidirectional BFS (BFS optimization for known source & target) — Optimize BFS by searching from both source and target simultaneously. Reduce time complexity significantly.
• Bridges & Articulation Points (Tarjan low-link) — Find bridges and articulation points in graphs using Tarjan's low-link algorithm.
• Minimum Spanning Tree (Kruskal / Prim / DSU + heap) — Find minimum spanning tree using Kruskal's or Prim's algorithm with Union-Find or heap.
• Strongly Connected Components (Kosaraju / Tarjan) — Find strongly connected components in directed graphs using Kosaraju's or Tarjan's algorithm.

Related DSA patterns

• Backtracking Patterns — Subsets, permutations, combinations, N-Queens, and word search.
• Dynamic Programming (DP) Patterns — Fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break.
• Bit Manipulation Patterns — XOR tricks, counting bits, power-of-two checks, and Hamming weight.
• Design Patterns — Tries, LRU/LFU cache, and data structure design.

Where to go next

Union-Find (Disjoint Set Union - DSU) is one lesson in a 16-pattern DSA course. If you are preparing end to end, work the interview-critical patterns first and use the pattern sheet as the checklist; if you are here for one technique, the Graph Traversal Patterns (DFS & BFS) guide is the shortest path back to the rest of it.

• The Graph Traversal Patterns (DFS & BFS) pattern guide
• All DSA patterns
• The DSA patterns sheet
• Coding practice