Kosaraju Algorithm In Python

Kosaraju.py

# Find Strongly Connected Components in a Graph using Kosaraju Algo

# Reference : https://www.youtube.com/watch?v=Rs6DXyWpWrI

from typing import List, Set

class Solution():
    
    def reverseEdges(self, edges: List[List[int]]) -> List:
        edges_rev = [list() for _ in range(len(edges))]
        for i, connections in enumerate(edges):
            for connection in connections:
                edges_rev[connection].append(i)
        return edges_rev

    def dfs(self, edges: List[List[int]], curr_node: int, is_visited: Set, stack: List):
        if curr_node in is_visited:
            return
        is_visited.add(curr_node)
        for connection in edges[curr_node]:
            self.dfs(edges, connection, is_visited, stack)
        stack.append(curr_node)
        return

    def scc(self, edges: List[List[int]]):
        print(edges)

        is_visited = set()
        stack = list()
        for i in range(len(edges)):
            if i not in is_visited:
                self.dfs(edges, i, is_visited, stack)

        edges_rev = self.reverseEdges(edges)
        is_visited.clear()
        old_stack = stack.copy()
        stack.clear()
        while len(old_stack):
            node = old_stack.pop()
            if node not in is_visited:
                self.dfs(edges_rev, node, is_visited, stack)
                print(sorted(stack))
                stack.clear()
        return

edge_list = []
edge_list.append([1]) # 0 
edge_list.append([2]) # 1
edge_list.append([0,3]) # 2
edge_list.append([4]) # 3
edge_list.append([5,7]) # 4
edge_list.append([6]) # 5
edge_list.append([4,7]) # 6
edge_list.append([]) # 7
solution = Solution()
solution.scc(edge_list)