https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

tarjan_scc.py

from collections import deque, defaultdict


def tarjan_recursive(graph):
    unvisited = set(graph.keys())
    low_link = {}
    visited_ids = {}  # Node id, also keep track of visited node
    stack_set = set()
    stack = []
    groups = []

    def strong_connect(node):
        visited_ids[node] = low_link[node] = len(visited_ids)
        stack_set.add(node)
        stack.append(node)
        unvisited.discard(node)

        for neighbor in graph.get(node, ()):
            if neighbor not in visited_ids:
                strong_connect(neighbor)
                low_link[node] = min(low_link[node], low_link[neighbor])
            elif neighbor in stack_set:
                low_link[node] = min(low_link[node], visited_ids[neighbor])

        if low_link[node] == visited_ids[node]:
            scc = []
            current = None
            while stack and current != node:
                current = stack.pop()
                scc.append(current)
                stack_set.discard(current)
            groups.append(scc)

    while unvisited:
        node = unvisited.pop()
        strong_connect(node)
    return groups, low_link
  
  
  graph = {
    'A': ['B', 'E'],
    'B': ['F'],
    'C': ['B', 'D', 'G'],
    'D': ['G'],
    'E': ['A', 'F'],
    'F': ['C', 'G'],
    'G': ['H'],
    'H': ['D']
}

graph2 = {
    1: [2],
    2: [3],
    3: [1],
    4: [2, 3, 5],
    5: [4, 6],
    6: [3, 7],
    7: [6],
    8: [5, 7, 8]
}