Leetcode 323. Number of Connected Components in an Undirected Graph

Problem Explanation:

This problem is asking to find the number of connected components in an undirected graph. The graph is represented by nodes and edges, where nodes are labeled from 0 to n - 1 and each edge is a pair of nodes. If you start from any node in a connected component, you can reach any other node in the same component through the given edges.

For example, if n = 5 and edges = [[0, 1], [1, 2], [3, 4]], this would represent two separate connected components, namely nodes 0-1-2 and nodes 3-4. Therefore, the output is 2.

Solution Approach:

The approach to solving this problem involves using a Breadth-First Search (BFS) algorithm to visit all reachable nodes from a starting node, marking them as visited as we go. We also keep track of the total number of connected components and increment it every time we encounter a node not reachable from any previously visited node.

The BFS function begins at a starting node, adds it to a queue, and marks it as visited. It then enters a while loop, removing a node from the queue, and adding all non-visited neighbors of that node to the queue. The function continues to do this until there are no more nodes in the queue.

The main function loops over all nodes and runs the BFS function on any node that's not been visited yet. Each time BFS is run, it increments the number of connected components.

Python Solution:

1
2python
3from collections import deque
4class Solution:
5    def countComponents(self, n: int, edges: List[List[int]]) -> int:
6        graph = [[] for _ in range(n)]
7        visited = [0] * n
8        cnt = 0  # number of connected components
9        
10        # build graph
11        for u, v in edges:
12            graph[u].append(v)
13            graph[v].append(u)
14            
15        # BFS
16        def bfs(i: int) -> None:
17            queue = deque([i])
18            while queue:
19                node = queue.popleft()
20                visited[node] = 1
21                for j in graph[node]:
22                    if visited[j] == 0:
23                        queue.append(j)
24                        
25        # visit all nodes, run BFS on unvisited
26        for i in range(n):
27            if visited[i] == 0:
28                bfs(i)
29                cnt += 1
30                
31        return cnt

Java Solution:

1
2java
3import java.util.*;
4class Solution {
5    public int countComponents(int n, int[][] edges) {
6        List<List<Integer>> graph = new ArrayList<>();
7        for (int i = 0; i < n; i++) {
8            graph.add(new ArrayList<>());
9        }
10        for (int[] edge : edges) {
11            graph.get(edge[0]).add(edge[1]);
12            graph.get(edge[1]).add(edge[0]);
13        }
14        int count = 0;
15        boolean[] visited = new boolean[n];
16        for (int i = 0; i < n; i++) {
17            if (!visited[i]) {
18                count++;
19                Queue<Integer> queue = new LinkedList<>();
20                queue.add(i);
21                while (!queue.isEmpty()) {
22                    int node = queue.poll();
23                    visited[node] = true;
24                    for (int neighbor : graph.get(node)) {
25                        if (!visited[neighbor]) {
26                            queue.add(neighbor);
27                        }
28                    }
29                }
30            }
31        }
32        return count;
33    }
34}

JavaScript Solution:

1
2javascript
3var countComponents = function(n, edges) {
4    const graph = Array.from({length: n}, () => []);
5    const visited = new Array(n).fill(false);
6    let count = 0;
7    for (let edge of edges) {
8        graph[edge[0]].push(edge[1]);
9        graph[edge[1]].push(edge[0]);
10    }
11    const bfs = (i) => {
12        let queue = [i];
13        while (queue.length) {
14            let node = queue.shift();
15            visited[node] = true;
16            for (let neighbor of graph[node]) {
17                if (!visited[neighbor]) {
18                    queue.push(neighbor);
19                }
20            }
21        }
22    };
23    for (let i = 0; i < n; i++) {
24        if (!visited[i]) {
25            bfs(i);
26            count++;
27        }
28    }
29    return count;
30};

In all three solutions above, the algorithm starts by creating an adjacency list to represent the graph using the provided edges. Then, it initializes a visited array to keep track of which nodes have been visited and a variable to count the connected components.

The algorithm then iterates over all nodes and runs a breadth-first search (BFS) on any node that hasn't been visited yet. The BFS function marks nodes as visited as they are encountered and adds unvisited neighbors to a queue to be searched next.

The BFS function continues until there are no more nodes in the queue. Every time a new BFS is started, it means a new connected component is found, so the count is incremented.

Finally, the algorithm returns the count as the number of connected components.

The BFS ensures all nodes in a connected component are visited before moving onto the next component. This approach ensures that every new BFS represents a unique connected component, making it easy to count the number of distinct components.

The logarithmic complexity of the algorithm is O(n + e), where n is the number of nodes and e is the number of edges. This is because each node and edge is visited once.

In conclusion, this problem is a classical graph exploration problem, and it can be solved efficiently through graph traversal techniques like BFS or DFS in any programming language. Here we illustrated how to solve it in Python, Java, and JavaScript, but the logic will stay the same across other languages. It's a good exercise for understanding graphs and traversal methods.