LC 0323 [M] Number of Connected Components in an Undirected Graph - ALawliet/algorithms GitHub Wiki
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
G = {i: set() for i in range(n)}
for u, v in edges:
G[u].add(v) ; G[v].add(u)
visited = set()
def dfs(u):
visited.add(u)
for v in G[u]:
if v not in visited:
dfs(v)
num_components = 0
for i in range(n):
if i not in visited:
num_components += 1
dfs(i)
return num_components
same algo as Number of Islands
from queue import Queue
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
# the edges are not the neighbors but the connections
# so have to use this info to build the adj map of neighbors
# python set() is implemented as hashtable with O(1) lookups
G = {v: set() for v in range(n)}
for v1, v2 in edges:
# if v1 is connected to v2, then v2 is also connected to v1
G[v1].add(v2) ; G[v2].add(v1)
print(G)
def bfs(v):
Q = Queue()
Q.put(v)
visited.add(v)
while not Q.empty():
node = Q.get()
for neighbor in G[node]:
if neighbor not in visited:
visited.add(neighbor)
Q.put(neighbor)
def dfs(node):
visited.add(node)
for neighbor in G[node]:
if neighbor not in visited:
dfs(neighbor)
visited = set()
num_components = 0
for v in range(n):
if v not in visited:
num_components += 1
bfs(v)
# dfs(v)
return num_components
DFS/BFS can also be used to find connected components, so screw union-find, which was made exactly for connected components/disjoint sets problem
O(n) implicit + O(m) explicit
where n is the stack/queue push/pop
trees m = n - 1
= O(m+n)
union-find can handle the edges coming in any order, useful if they cannot fit in memory
https://www.youtube.com/watch?v=8f1XPm4WOUc&ab_channel=NeetCode
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
parent = [i for i in range(n)]
rank = [1] * n
def find(n1):
cur = n1
while cur != parent[cur]:
parent[cur] = parent[parent[cur]] # optimization: path compression (not needed)
cur = parent[cur]
return cur
def union(n1, n2):
p1, p2 = find(n1), find(n2)
if p1 == p2:
return 0
if rank[p1] > rank[p2]:
parent[p2] = p1 # union child to higher rank parent
rank[p1] += rank[p2] # increase the rank of parent
else:
parent[p1] = p2
rank[p2] += rank[p1]
return 1
num_connected = n
for n1, n2 in edges:
num_connected -= union(n1, n2) # -1 from n whenever we get a successful union
return num_connected