Skip to main content

🟨 Number of Connected Components in an Undirected Graph (#323) 🔒

🔗 Problem Link​

📋 Problem Statement​

Given n nodes labeled from 0 to n - 1 and a list of undirected edges, write a function to find the number of connected components in an undirected graph.

Note: This is a premium LeetCode problem, but available for free on NeetCode.

💡 Examples​

Example 1​

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

Example 2​

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

🔑 Key Insights & Approach​

Core Observation: Use DFS/BFS to find connected components or Union-Find to merge nodes.

Why Union-Find?

  • O(n + e * α(n)) time with path compression
  • O(n) space
  • Natural fit for component counting

Approaches:

  1. DFS/BFS: O(n + e) time, O(n) space
  2. Union-Find: O(n + e * α(n)) time, O(n) space - optimal

Pattern: "Connected Components" using Union-Find or DFS.

🐍 Solution: Python​

Approach 1: Union-Find​

Time Complexity: O(n + e * α(n)) | Space Complexity: O(n)

from typing import List

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = list(range(n))

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[px] = py
                return True
            return False

        components = n
        for u, v in edges:
            if union(u, v):
                components -= 1

        return components

Approach 2: DFS​

Time Complexity: O(n + e) | Space Complexity: O(n)

from typing import List
from collections import defaultdict

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = set()
        components = 0

        def dfs(node):
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor)

        for node in range(n):
            if node not in visited:
                dfs(node)
                components += 1

        return components

🔵 Solution: Golang​

Approach: Union-Find​

Time Complexity: O(n + e * α(n)) | Space Complexity: O(n)

func countComponents(n int, edges [][]int) int {
    parent := make([]int, n)
    for i := range parent {
        parent[i] = i
    }

    var find func(x int) int
    find = func(x int) int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    union := func(x, y int) bool {
        px, py := find(x), find(y)
        if px != py {
            parent[px] = py
            return true
        }
        return false
    }

    components := n
    for _, edge := range edges {
        if union(edge[0], edge[1]) {
            components--
        }
    }

    return components
}

📚 References​