Number of Connected Components in an Undirected Graph medium

Problem Statement

You have been given an undirected graph represented as an integer array n representing the number of nodes and a 2D integer array edges where each edges[i] = [u, v] indicates that there is an undirected edge between nodes u and v. You are tasked to find the number of connected components in the graph. A connected component is a subset of the graph where every node is reachable from every other node within the subset.

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 only one connected component: {0,1,2,3,4}.

Steps

1. Initialization: Create an adjacency list to represent the graph. Initialize a visited set to keep track of visited nodes. The number of connected components is initialized to 0.

2. Depth-First Search (DFS): Iterate through each node in the graph. If a node hasn't been visited, perform a DFS starting from that node. The DFS will explore all reachable nodes from the current node, marking them as visited. Each time a DFS is initiated from an unvisited node, it signifies a new connected component.

3. Counting Components: Increment the count of connected components after each DFS call.

4. Return: Return the final count of connected components.

Explanation

The algorithm uses Depth-First Search (DFS) to explore the graph. DFS systematically visits all nodes reachable from a starting node. By starting a DFS from each unvisited node, we ensure that all connected components are identified. Each time a DFS is initiated from an unvisited node, it means we've found a new unconnected part of the graph.

Code

def countComponents(n, edges):
    """
    Counts the number of connected components in an undirected graph.

    Args:
        n: The number of nodes in the graph.
        edges: A list of edges, where each edge is a list of two node indices.

    Returns:
        The number of connected components in the graph.
    """

    adj_list = [[] for _ in range(n)]  # Adjacency list to represent the graph
    for u, v in edges:
        adj_list[u].append(v)
        adj_list[v].append(u)  # Undirected graph, add edge in both directions

    visited = set()  # Keep track of visited nodes
    count = 0  # Count of connected components

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

    for i in range(n):
        if i not in visited:
            dfs(i)
            count += 1

    return count

Complexity

• Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges. This is because the DFS visits each node and edge at most once.

• Space Complexity: O(V), dominated by the visited set and the adjacency list. In the worst-case scenario (a complete graph), the adjacency list will store V * (V-1) / 2 entries. However, on average and for sparse graphs, it's approximately O(V).