Tarjan Algorithm In Python

Tarjan.py

# Reference : https://www.youtube.com/watch?v=ZeDNSeilf-Y

from typing import List

class Solution():

    def __init__(self) -> None:
        self.timer = 0
        self.discovery = []
        self.low = []
        self.instack = []
        return
    
    def dfs(self, edges: List[List[int]], currNode: int, stack: List):

        # Assign the current timer
        self.discovery[currNode] = self.timer
        self.low[currNode] = self.timer
        self.timer = self.timer + 1
        stack.append(currNode)
        self.instack[currNode] = True

        # For all neighbors
        for nextNode in edges[currNode]:

            if self.discovery[nextNode] == -1: # Not yet not discovered
                self.dfs(edges, nextNode, stack)
                self.low[currNode] = min(self.low[currNode], self.low[nextNode]) # For normal edge
            else:
                if self.instack[nextNode]: # It is a back edge
                    self.low[currNode] = min(self.low[currNode], self.discovery[nextNode])
                else: # It is a cross edge
                    pass # Do nothing
        
        # Pop if current node is head node for strongly connected component
        if self.discovery[currNode] == self.low[currNode]:
            scc = []
            while stack:
                n = stack.pop()
                self.instack[n] = False
                scc.append(n)
                if n == currNode:
                    break
            print(scc)
                
        return

    def tarjan_algo(self, edges: List[List[int]]):
        e = len(edges)

        if e:

            # Initialize
            self.discovery = [-1 for _ in range(e)]
            self.low = [-1 for _ in range(e)]
            self.instack = [False for _ in range(e)]

            # Run DFS for all disconnected components
            stack = []
            for n in range(e):
                if self.discovery[n] == -1:
                    self.dfs(edges, n, stack)

        return

# DAC
edges = [[1], [2,3], [], [4], [0, 5, 6], [2,6], [5]]
solution = Solution()
solution.tarjan_algo(edges)