Graph DFS - Connected Components / Island Counting — Graph Traversal Patterns (DFS & BFS)

The Graph DFS - Connected Components / Island Counting pattern applies when you need the Graph DFS - Connected Components / Island Counting technique within the Graph Traversal Patterns (DFS & BFS) pattern. Its time complexity is O(V + E) and space complexity O(V). It is used in 11 problems on Thita, including Count Sub Islands, Detonate the Maximum Bombs and Flood Fill. Common variations are Graph DFS - Cycle Detection (Directed Graph) and Deep Copy / Cloning.

Use DFS to find connected components and count islands in grids. Flood fill and province counting problems.

Graph DFS - Connected Components / Island Counting 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 core technique: expect it to come up directly in interviews.

What Graph DFS - Connected Components / Island Counting 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 number of islands, connected components, flood fill, DFS graph, leetcode 200, leetcode 547.

How to practise Graph DFS - Connected Components / Island Counting on Thita.ai

Read the theory for Graph DFS - Connected Components / Island Counting, 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 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.
• Union-Find (Disjoint Set Union - DSU) — Master Union-Find data structure with path compression and union by rank for connectivity problems.
• 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

Graph DFS - Connected Components / Island Counting 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