What are Connected Components?

A connected component is a maximal set of nodes where a path exists between every pair of nodes in the set.

How to count components?

Start a traversal (BFS/DFS) from an unvisited node, mark all reachable nodes, and increment the count. Repeat until all nodes are visited.

Strongly vs Weakly Connected?

Only applicable to directed graphs. "Strongly" means a bidirectional path exists between all pairs. "Weakly" means the underlying undirected graph is connected.

Connected Components

Learn how to find and count connected components in an undirected graph using BFS or DFS. Useful for social network analysis and image segmentation.

Ready to start

Speed

See the Logic in Motion

Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.

Unlock VisualizerPREMIUM FEATURE

Intuition

Imagine a group of islands. You can walk anywhere on a single island, but you can't walk to another island without swimming.

Each island is a Connected Component.

Graph traversal algorithms like BFS or DFS can explore one entire island before moving to the next.

Concept

Connected Component: A subgraph where every node is reachable from every other node in that subgraph.
Traversal: To find all components, we iterate through every node. If a node hasn't been visited, it belongs to a new component. We then traverse (BFS/DFS) to find all nodes in that component.

How it Works

Algorithm Steps:

Initialize count = 0 and a visited set.
Iterate through all nodes i from 0 to N-1.
If node i is NOT visited:
- Increment count.
- Start a traversal (BFS or DFS) from node i.
- Mark all reachable nodes as visited.
Return count.

Step-by-Step Breakdown

Watch the visualization:

White Node: Currently being visited.
Colored Node: Assigned to a specific component. Different components have different colors.

When to Use

Use Connected Components when:

Counting distinct groups in a social network (e.g., groups of friends).
Image segmentation (grouping connected pixels).
Finding isolated systems or unreachable servers in a network.

When NOT to Use

Directed Graphs: For directed graphs, you typically look for Strongly Connected Components (SCC) or Weakly Connected Components, which require different algorithms (like Tarjan's or Kosaraju's).

How to Identify

Problems asking to "count groups", "count provinces", "number of islands", or "check path existence" often relate to connected components.

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep