Number of Connected Components in an Undirected Graph

Problem Statement

There is an undirected graph with n nodes. There is also an edges array, where edges[i] = [a, b] means that there is an edge between node a and node b in the graph.

The nodes are numbered from 0 to n - 1.

Return the total number of connected components in that graph.

Example 1:

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


Output:
1

Example 2:

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


Output:
2

Constraints:

  • 1 <= n <= 100
  • 0 <= edges.length <= n * (n - 1) / 2

You should aim for a solution as good or better than O(V + E) time and O(V + E) space, where V is the number of vertices and E is the number of edges in the graph.

You should aim for a solution as good or better than O(V + E) time and O(V + E) space, where V is the number of vertices and E is the number of edges in the graph.

Hint 1

Assume there are no edges initially, so we have n components, as there are that many nodes given. Now, we should add the given edges between the nodes. Can you think of an algorithm to add the edges between the nodes? Also, after adding an edge, how do you determine the number of components left?

Hint 2

We can use the Union-Find (DSU) algorithm to add the given edges. For simplicity, we use Union-Find by size, where we merge the smaller component into the larger one. The Union-Find algorithm inserts the edge only between two nodes from different components. It does not add the edge if the nodes are from the same component. How do you find the number of components after adding the edges? For example, consider that nodes 0 and 1 are not connected, so there are initially two components. After adding an edge between these nodes, they become part of the same component, leaving us with one component.

Hint 3

We create an object of the DSU and initialize the result variable res = n, which indicates that there are n components initially. We then iterate through the given edges. For each edge, we attempt to connect the nodes using the union function of the DSU. If the union is successful, we decrement res; otherwise, we continue. Finally, we return res as the number of components.

Solution

def count_components_dfs(n: int, edges: list[list[int]]) -> int:
    """
    Counts the number of connected components in a graph using Depth-First Search.
    """
    adj = [[] for _ in range(n)]
    visited = [False] * n
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)


    def dfs(node: int):
        visited[node] = True
        for neighbor in adj[node]:
            if not visited[neighbor]:
                dfs(neighbor)


    count = 0
    for node in range(n):
        if not visited[node]:
            dfs(node)
            count += 1
    return count

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

from collections import deque


def count_components_bfs(n: int, edges: list[list[int]]) -> int:
    """
    Counts the number of connected components in a graph using Breadth-First Search.
    """
    adj = [[] for _ in range(n)]
    visited = [False] * n
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)


    def bfs(node: int):
        queue = deque([node])
        visited[node] = True
        while queue:
            current = queue.popleft()
            for neighbor in adj[current]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)


    count = 0
    for node in range(n):
        if not visited[node]:
            bfs(node)
            count += 1
    return count

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

Disjoint Set Union (Rank | Size)

class DSU:
    """
    Disjoint Set Union data structure with rank and path compression.
    """
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [1] * n


    def find(self, node: int) -> int:
        """
        Finds the representative of the set that the node belongs to with path compression.
        """
        if node != self.parent[node]:
            self.parent[node] = self.find(self.parent[node])  # Path compression
        return self.parent[node]


    def union(self, u: int, v: int) -> bool:
        """
        Unions the sets containing nodes u and v by rank.
        Returns True if the sets were different, False otherwise.
        """
        root_u = self.find(u)
        root_v = self.find(v)


        if root_u == root_v:
            return False  # Already in the same set


        if self.rank[root_u] < self.rank[root_v]:
            root_u, root_v = root_v, root_u  # Swap to ensure root_u has higher rank


        self.parent[root_v] = root_u  # Attach smaller rank tree under higher rank tree
        self.rank[root_u] += self.rank[root_v]  # Update rank


        return True  # Sets were different


def count_components_dsu(n: int, edges: list[list[int]]) -> int:
    """
    Counts the number of connected components in a graph using Disjoint Set Union.
    """
    dsu = DSU(n)
    count = n
    for u, v in edges:
        if dsu.union(u, v):
            count -= 1
    return count

Time complexity: O(V + (E * A(V))) Space complexity: O(V)