def dfs(visited,graph,stack,root):
visited.add(root)
for neighbour in graph[root]:
if neighbour not in visited:
dfs(visited,graph,stack,neighbour)
stack.append(root)
return stack
def dfs_on_reverse(node, visit, component):
visit.add(node)
component.append(node)
for neighbour in reverse_graph[node]:
if neighbour not in visit:
dfs_on_reverse(neighbour, visit, component)
graph = {
1: [2],
2: [3],
3: [1, 4],
4: [5],
5: [6],
6: [4],
7: [6, 8],
8: [7]
}
stack=[]
visited=set()
for node in graph:
if node not in visited:
dfs(visited, graph, stack, node)
reverse_graph={}
for node in graph:
for neighbour in graph[node]:
reverse_graph.setdefault(neighbour, []).append(node)
visit=set()
while stack:
node = stack.pop()
if node not in visit:
component = []
dfs_on_reverse(node, visit, component)
print("SCC:", component)
