323. Number of Connected Components in an Undirected Graph

This problem asks to find the number of connected components in an undirected graph given the number of nodes and edges. We can solve this using Depth-First Search (DFS), Breadth-First Search (BFS), or Union-Find.

Solutions

1. Depth-First Search (DFS)

Approach:

DFS recursively explores the graph starting from an unvisited node. It marks each visited node and continues exploring its neighbors until no unvisited neighbors are left. Each time a DFS call completes from an unvisited node, it signifies finding a connected component.

Algorithm:

1. Initialization: Create an adjacency list to represent the graph. Initialize a visited set to keep track of visited nodes.
2. Iteration: Iterate through all nodes (0 to n-1).
3. DFS Call: For each unvisited node, call a recursive DFS function.
4. DFS Function:
   • Mark the current node as visited.
   • Recursively call DFS for each unvisited neighbor.
   • Return 1 (representing one connected component found).
5. Counting: The total number of connected components is the sum of the returns from the DFS calls.

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

Space Complexity: O(V + E) in the worst case (due to recursion stack in DFS and adjacency list).

Code (Python):

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
 
        visited = set()
        count = 0
 
        def dfs(node):
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor)
 
        for i in range(n):
            if i not in visited:
                dfs(i)
                count += 1
        return count

Other languages (Java, C++, Go, TypeScript, JavaScript) would follow a similar structure, adapting the syntax accordingly.

2. Breadth-First Search (BFS)

Approach:

BFS uses a queue to explore the graph level by level. It starts from an unvisited node, adds it to the queue, and then iteratively explores its neighbors, adding them to the queue if they are unvisited. Like DFS, each completed BFS traversal from an unvisited node represents a connected component.

Algorithm: Similar to DFS, but uses a queue instead of recursion.

Time Complexity: O(V + E), same as DFS.

Space Complexity: O(V) (queue can hold at most all the nodes in a component).

Code (Python):

from collections import deque
 
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
 
        visited = set()
        count = 0
 
        for i in range(n):
            if i not in visited:
                count += 1
                queue = deque([i])
                while queue:
                    node = queue.popleft()
                    visited.add(node)
                    for neighbor in graph[node]:
                        if neighbor not in visited:
                            queue.append(neighbor)
        return count
 

3. Union-Find (Disjoint Set Union)

Approach:

Union-Find is a data structure that efficiently maintains disjoint sets. Each node initially represents its own set. When an edge is processed, the sets of its connected nodes are merged using the union operation. The number of remaining sets after processing all edges represents the number of connected components.

Algorithm:

1. Initialization: Create a Union-Find data structure with n nodes, each in its own set.
2. Union: For each edge (u, v), perform union(u, v) to merge the sets containing u and v.
3. Counting: The number of connected components is the number of sets remaining in the Union-Find data structure.

Time Complexity: Almost linear, O(α(n) * E), where α(n) is the inverse Ackermann function, which is very slow-growing and can be considered a constant for practical purposes. Union-Find operations are very fast on average.

Space Complexity: O(n)

Code (Python):

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
 
    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])  # Path compression
        return self.parent[i]
 
    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            self.parent[root_i] = root_j
            return True
        return False
 
class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        uf = UnionFind(n)
        for u, v in edges:
            uf.union(u, v)
        
        count = 0
        for i in range(n):
            if uf.find(i) == i:
                count += 1
        return count

Union-Find generally offers the best performance for this problem, especially for larger graphs, due to its near-linear time complexity. DFS and BFS are simpler to implement but have a slightly higher time complexity in the worst case. Choose the method that best suits your needs and familiarity.