TIC
The Interns Company

Number of Connected Components in an Undirected Graph

MediumAcceptance: 57.2%
GraphUnion FindDFSBFS

Problem Statement

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph. Return the number of connected components in the graph.

Constraints:

  • 1 <= n <= 2000
  • 1 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai <= bi < n
  • ai != bi
  • There are no repeated edges.

Input Format:

  • An integer n representing the number of nodes (labeled from 0 to n-1)
  • A 2D array edges where each element is an edge between two nodes

Output Format:

  • Return the number of connected components in the graph.

Examples:

Example 1:

Input:

n = 5, edges = [[0,1],[1,2],[3,4]]

Output:

2

Explanation:

There are two connected components: [0,1,2] and [3,4].

Example 2:

Input:

n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]

Output:

1

Explanation:

There is one connected component: [0,1,2,3,4].

Solutions

Union Find (Disjoint Set) Approach

Time: O(E·α(n))
Space: O(n)

Use a Union-Find data structure to track connected components. Initially, each node is in its own set. Process each edge and union the sets containing the two nodes. The number of connected components is the number of distinct sets at the end.

DFS Approach

Time: O(V + E)
Space: O(V + E)

Use Depth First Search to traverse the graph. For each unvisited node, start a DFS and mark all nodes in its connected component as visited. The number of times you need to start a new DFS is the number of connected components.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Build an adjacency list or prepare Union-Find structures
  2. For Union-Find: Initially each node is in its own component (5 components)
  3. Process edge [0,1]: Union nodes 0 and 1 (4 components remain)
  4. Process edge [1,2]: Union nodes 1 and 2 (3 components remain)
  5. Process edge [3,4]: Union nodes 3 and 4 (2 components remain)
  6. Final connected components: [0,1,2] and [3,4]
  7. Return count: 2

Hints

Hint 1
You can use either a Union-Find (Disjoint Set) data structure or graph traversal algorithms (DFS/BFS) to solve this problem.
Hint 2
For Union-Find, initially, each node is in its own component. As you process edges, you merge components.
Hint 3
For DFS/BFS, you can start from each unvisited node and mark all reachable nodes as visited, counting the number of times you need to start a new traversal.

Video Tutorial

Number of Connected Components - Union Find & DFS Approaches

YouTube•Learn the Number of Connected Components in an Undirected Graph solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the graph and its connected components, highlighting different components with different colors.

Key visualization elements:

  • nodes
  • edges
  • connected components

Similar Questions

Graph Valid Tree

Medium

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph. Return true if the graph is a valid tree, or false otherwise.

Number of Islands

Medium

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Asked By

AmazonFacebookMicrosoftGoogleBloombergUber

Implementation Notes

This problem is a good introduction to union-find and graph traversal techniques. It's commonly used to test understanding of graph connectivity concepts.