scc kosaraju Algorithm
The SCC Kosaraju Algorithm is a linear time algorithm used to find strongly connected components (SCCs) in a directed graph. Strongly connected components in a graph are subgraphs where every pair of vertices within the subgraph are connected by a directed path in both directions. In other words, for every pair of vertices (u, v) in a strongly connected component, there exists a path from u to v and a path from v to u. The algorithm, named after its inventor, S. Rao Kosaraju, is based on the idea of depth-first search (DFS) traversal and utilizes two DFS calls to efficiently find SCCs in a given graph.
The Kosaraju Algorithm comprises of three main steps: first, perform a DFS traversal on the original graph and maintain a stack of visited vertices in the order they get traversed; second, transpose the original graph by reversing the direction of all edges; finally, perform a DFS traversal on the transposed graph, starting with the vertices in the stack obtained in the first step, and pop the vertices from the stack as they are visited. The SCCs are identified during this final DFS traversal, where each DFS call identifies a single strongly connected component. The Kosaraju Algorithm has a time complexity of O(V + E), where V represents the number of vertices and E represents the number of edges in the graph, making it an efficient algorithm for finding SCCs in large graphs.
def dfs(u):
global g, r, scc, component, visit, stack
if visit[u]:
return
visit[u] = True
for v in g[u]:
dfs(v)
stack.append(u)
def dfs2(u):
global g, r, scc, component, visit, stack
if visit[u]:
return
visit[u] = True
component.append(u)
for v in r[u]:
dfs2(v)
def kosaraju():
global g, r, scc, component, visit, stack
for i in range(n):
dfs(i)
visit = [False] * n
for i in stack[::-1]:
if visit[i]:
continue
component = []
dfs2(i)
scc.append(component)
return scc
if __name__ == "__main__":
# n - no of nodes, m - no of edges
n, m = list(map(int, input().strip().split()))
g = [[] for i in range(n)] # graph
r = [[] for i in range(n)] # reversed graph
# input graph data (edges)
for i in range(m):
u, v = list(map(int, input().strip().split()))
g[u].append(v)
r[v].append(u)
stack = []
visit = [False] * n
scc = []
component = []
print(kosaraju())
