Number of Connected Components in Undirected Graph
- 1 min read
- Graph
- LC-Medium
3 years ago
Solution
- Do a Union Find and each time you union two components, reduce the number of connected components by 1. Initially the number of connected components would be equal to the number of vertices in the graph.
| Time | Space | Explanation |
|---|---|---|
O(v + e) | O(v) |
def countComponents(self, n: int, edges: List[List[int]]) -> int:
par = {i: i for i in range(n)}
rank = {i: 1 for i in range(n)}
def find(n):
n = par[n]
while n != par[n]:
par[n] = par[par[n]]
n = par[n]
return n
def union(a, b):
p1, p2 = find(a), find(b)
if p1 == p2:
return False
if rank[p1] > rank[p2]:
rank[p1] += rank[p2]
par[p2] = p1
else:
rank[p2] += rank[p1]
par[p1] = p2
return True
for a, b in edges:
if union(a, b):
n -= 1
return n