Strongly Connected Components Problem#

Find the partition of such that all vertices in each partition are reachable from each other and that each partition is maximal. Each partition is a strongly connected component.

Theory#

As shown in ⏱️ Finish-Time DFS, a source vertex must have larger DFS finish times than other vertices.

Then, in , such a vertex must be a sink; running DFS on in finds the strongly connected component that it’s in, and we can move on to the next vertex with largest finish time that’s not in .

Implementation#

t = 0

def kosaraju(adj):
	vis, fin = set(), []
	for s in range(len(adj)):
		if s not in vis:
			dfs1(s, adj, vis, fin)

	adj_t = {}
	for i in range(len(adj)):
		adj_t[u] = []
	for u in adj:
		for v in adj[u]:
			adj[v].append(u)

	ret, vis = [], set()
	for _, s in reversed(fin):
		if s not in vis:
			comp = set()
			dfs2(s, adj_t, vis comp)
			ret.append(comp)
	return ret

def dfs1(s, adj, vis, fin):
	vis.add(s)
	for n in adj[s]:
		if n not in vis:
			dfs1(n, adj, vis)
	fin.append((t, s))
	t += 1

def dfs2(s, adj, vis, comp):
	vis.add(s)
	comp.add(s)
	for n in adj[s]:
		if n not in vis:
			dfs2(n, adj, vis, comp)

Runtime#

We essentially perform two runs of DFS, so our algorithm takes .