3651. Number of Connected Components in an Undirected Graph#

Difficulty: Medium

Link to Problem: To see the Number of Connected Components in an Undirected Graph problem on LintCode, click here!

In this problem, 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.

You need to return the number of connected components in that graph.

Probelm Explanation:#

The problem at hand is to determine the number of connected components in an undirected graph. Here’s a more detailed explanation of the problem:

  • You are given an undirected graph, which consists of nodes and edges. The graph may have multiple distinct connected components.

  • A connected component is a group of nodes within the graph where each node can be reached from every other node in the same component. In other words, there is a path between any two nodes in the same connected component, but there are no paths connecting nodes from different components.

  • Your task is to write a function that takes as input the number of nodes n and a list of edges edges, where each edge is represented as a pair of nodes [a, b] indicating an edge between node a and node b.

  • The goal is to determine the number of distinct connected components in the graph.

  • You need to implement an algorithm that can identify these connected components and count how many there are in the given graph.

Solution:#

Here’s a Python function to implement this algorithm:

def countConnectedComponents(n, edges):
    # Define a helper function for depth-first search (DFS).
    def dfs(node):
        if not visited[node]:  # If the node has not been visited yet:
            visited[node] = True  # Mark it as visited.
            for neighbor in graph[node]:  # Explore all neighbors of the current node.
                dfs(neighbor)  # Recursively call DFS on the neighbor.

    # Create an empty adjacency list to represent the graph.
    graph = [[] for _ in range(n)]

    # Initialize a boolean list to keep track of visited nodes.
    visited = [False] * n

    # Populate the adjacency list with edges from the input.
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)  # Since the graph is undirected, we add edges in both directions.

    # Initialize a counter to keep track of the number of connected components.
    count = 0

    # Iterate through all nodes in the graph.
    for i in range(n):
        if not visited[i]:  # If the node has not been visited:
            count += 1  # Increment the count since we've found a new connected component.
            dfs(i)  # Start a depth-first search from the unvisited node to explore the component.

    return count

Explanation:#

The provided Python code calculates the number of connected components in an undirected graph. Here’s a high-level explanation of how the code works:

  1. The countConnectedComponents function takes two arguments: n (the number of nodes in the graph) and edges (a list of edge pairs representing connections between nodes).

  2. Inside the function, there is a helper function called dfs (depth-first search), which is used to explore and mark nodes as visited.

  3. An empty adjacency list called graph is created to represent the graph. The graph is a list of lists where each element represents a node, and the list associated with each node contains its neighboring nodes.

  4. Another list called visited is created to keep track of visited nodes. Initially, all nodes are marked as not visited (False).

  5. The code populates the graph by iterating through the edges list and adding each edge to the adjacency list. Since the graph is undirected, both directions of each edge are added.

  6. A counter variable called count is initialized to keep track of the number of connected components.

  7. The code iterates through all nodes from 0 to n-1. For each node, it checks whether it has been visited yet. If it hasn’t been visited, it means a new connected component is found. The counter count is incremented, and a depth-first search (DFS) is initiated from this unvisited node to explore the connected component.

  8. The dfs function recursively visits all nodes in the connected component, marking them as visited. It does this by checking each neighbor of the current node and recursively calling dfs on unvisited neighbors.

  9. After the loop through all nodes, the count variable contains the total number of connected components in the graph.

  10. The function returns the value of count, which represents the number of connected components.

  11. Two examples are provided at the end to demonstrate how to use the function with different inputs.

Test cases:#

Here’s how you can use this solution:

# Example 1
n1 = 3
edges1 = [[0, 1], [0, 2]]
print(countConnectedComponents(n1, edges1))  # Output: 1

1

# Example 2
n2 = 6
edges2 = [[0, 1], [1, 2], [2, 3], [4, 5]]
print(countConnectedComponents(n2, edges2))  # Output: 2

2

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the code for counting the number of connected components in an undirected graph using depth-first search (DFS).

Time Complexity:

  • The code iterates through all nodes in the graph (from 0 to n-1).

  • For each unvisited node, it initiates a depth-first search (DFS) from that node to explore the connected component.

  • In the worst case, every node may belong to a separate connected component, and you perform a DFS for each node.

  • The time complexity of the DFS for a single connected component is O(V + E), where V is the number of nodes in the component, and E is the number of edges.

  • In the worst case, you perform O(n) DFS calls, each with its own O(V + E) complexity.

So, the overall time complexity of the code is O(n * (V + E)). In the worst case, if the graph is connected (a single connected component), this simplifies to O(n * (n + m)), where m is the number of edges.

Space Complexity:

  • The main data structures used are the graph (adjacency list), visited (boolean array), and the recursive call stack for DFS.

  • The graph has a space complexity of O(n + m), where n is the number of nodes, and m is the number of edges.

  • The visited boolean array also has a space complexity of O(n) to keep track of whether nodes have been visited.

  • The depth of the recursive call stack for DFS can go up to O(n) in the worst case, when all nodes are part of a single connected component.

So, the overall space complexity of the code is O(n + m) for data structures and O(n) for the call stack. In the worst case, this simplifies to O(n + m).

In summary, the time complexity is O(n * (V + E)), and the space complexity is O(n + m).

Challenging Exercises:#

  1. Disconnected Components with Multiple Queries: You are given an undirected graph with n nodes and m edges. Initially, the graph is disconnected, and you need to process q queries. Each query consists of adding an edge to connect two nodes. After each query, you need to output the number of connected components in the updated graph.

  2. Maximum Size of Connected Components: Given an undirected graph with n nodes and m edges, find the size of the largest connected component in the graph. Additionally, identify the nodes that belong to this largest component. You can assume there is at least one connected component in the graph.