Number of Connected Components
Given an undirected graph, count the number of connected components.
Constraints:
- 1 <= n <= 2000
- 1 <= edges.length <= 5000
- edges[i].length == 2
- 0 <= edges[i][0] < n
- 0 <= edges[i][1] < n
- edges[i][0] != edges[i][1]
Examples:
Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
Output: 2
Explanation: There are 2 connected components: [0, 1, 2] and [3, 4].
Solutions
Depth-First Search (DFS)
Time: O(n + m)Space: O(n + m)
We use DFS to traverse the graph and count the number of connected components. We create an adjacency list representation of the graph and then iterate over all nodes. For each unvisited node, we perform a DFS traversal and increment the count of connected components.
def countComponents(n, edges):
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:
dfs(graph, visited, i)
count += 1
return count
def dfs(graph, visited, node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, visited, neighbor)Follow-up:
How would you solve this problem if the graph is very large and does not fit in memory?
