Number Of Connected Components In An Undirected Graph - Leetcode Solution

Problem Statement:

Given an undirected graph, return the number of connected components present in it.

Solution:

To solve this problem, we can use Depth-First Search (DFS).

Algorithm:

1. Initialize a list to mark if a node has been visited or not.
2. Initialize a variable to keep track of the number of connected components.
3. Iterate through all the nodes in the graph using a loop.
4. If a node has not been visited, perform a DFS starting from that node.
5. During the DFS, mark all the nodes that are visited.
6. Each DFS starting from an unvisited node will cover a completely new connected component, hence increment the count of connected components after each DFS.
7. After all the nodes have been visited, the count of connected components will be the answer.

Pseudo code:

function dfs(node, visited, adjacency_list): visited[node] = True for neighbor in adjacency_list[node]: if not visited[neighbor]: dfs(neighbor, visited, adjacency_list)

function count_connected_components(adjacency_list): visited = [False] * len(adjacency_list) count = 0 for node in range(len(adjacency_list)): if not visited[node]: dfs(node, visited, adjacency_list) count += 1 return count

Time Complexity: O(V+E), where V is the number of vertices and E is the number of edges in the graph.

Space Complexity: O(V), where V is the number of vertices.

Python Implementation:

class Solution: def countComponents(self, n: int, edges: List[List[int]]) -> int: adjacency_list = [[] for _ in range(n)] for edge in edges: adjacency_list[edge[0]].append(edge[1]) adjacency_list[edge[1]].append(edge[0])

    return self.count_connected_components(adjacency_list)

def dfs(self, node, visited, adjacency_list):
    visited[node] = True
    for neighbor in adjacency_list[node]:
        if not visited[neighbor]:
            self.dfs(neighbor, visited, adjacency_list)
            
def count_connected_components(self, adjacency_list):
    visited = [False] * len(adjacency_list)
    count = 0
    for node in range(len(adjacency_list)):
        if not visited[node]:
            self.dfs(node, visited, adjacency_list)
            count += 1
    return count

The above implementation correctly solves the problem and passes all the test cases.

1