Katkat
Back

Count Connected Components in an Undirected Graph

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to traverse an undirected graph using graph search algorithms to identify and count disjoint subgraphs.

Problem Statement

Given an integer n representing the number of nodes in an undirected graph labeled from 0 to n-1, and a list of edges where edges[i] = [u, v] indicates an undirected edge between nodes u and v, write a function to return the total number of connected components in the graph.

Function Signature

def count_connected_components(n: int, edges: list[list[int]]) -> int:

Constraints

  • 1 <= n <= 5000
  • 0 <= len(edges) <= 5000
  • Each edge consists of unique nodes within the range [0, n-1]

Examples

Example 1: Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]] Output: 2 Explanation: The components are {0, 1, 2} and {3, 4}.

Example 2: Input: n = 4, edges = [[0, 1], [2, 3]] Output: 2 Explanation: The components are {0, 1} and {2, 3}.

Edge Cases

  • A graph with no edges (each node is its own component).
  • A graph with no nodes (n=0).
  • A fully connected graph (1 component).

Hints

Hint 1

Represent the graph using an adjacency list where each node maps to a list of its neighbors.

Hint 2

Perform a traversal (BFS or DFS) starting from every unvisited node; each time you start a new traversal, you have found a new connected component.

Hint 3

Consider an alternative approach using the Disjoint Set Union (DSU/Union-Find) data structure to keep track of merged sets as you process each edge.

Follow-up questions

  • How would you modify your solution to determine if the graph contains any cycles?
  • What is the time and space complexity of your implementation in terms of V (vertices) and E (edges)?
  • How would your approach change if the graph were directed and you needed to find strongly connected components?