from typing import Mapping, List


class StronglyConnectedComponents:
    def __init__(self) -> None:
        self.reset_dfs_vars()

    def reset_dfs_vars(self) -> None:
        self.finishing_time = 1
        self.finishing_order = []
        self.explored = set([])
        self.source_node = None
        self.components = {}

    def reverse_graph(self, graph: Mapping[int, List[int]]) -> Mapping[int, List[int]]:
        reversed_graph = {}
        for node in graph:
            edge_list = graph[node]
            for adj_node in edge_list:
                try:
                    reversed_graph[adj_node].append(node)
                except KeyError:
                    reversed_graph[adj_node] = [node]

        return reversed_graph

    def strongly_connected_components(self, graph: Mapping[int, List[int]]) -> List[int]:
        """
        Given a directed graph, return an array of its strongly connected components.
        A strongly connected component is a collection of nodes where each node is reachable from every other node.

        This implementation assumes the inputted graph is an adjacency list of nodes.
        """
        reversed_graph = self.reverse_graph(graph)
        for node in reversed_graph:
            if node not in self.explored:
                self.dfs(reversed_graph, node)
        reversed_order = reversed(self.finishing_order)
        self.reset_dfs_vars()

        for node in reversed_order:
            if node not in self.explored:
                self.source_node = node
                self.dfs(graph, node)

        res = self.components.values()
        self.reset_dfs_vars()
        return res

    def dfs(self, graph: Mapping[int, List[int]], node: int) -> None:
        """
        Depth first search that:
        1. Updates the global variable finishing_order with order each node finished processing.
        2. Updates the global variable components, associating each node with its source node.
        """
        self.explored.add(node)
        try:
            self.components[self.source_node].append(node)
        except KeyError:
            self.components[self.source_node] = [node]
        for adj_node in graph[node]:
            if adj_node not in self.explored:
                self.dfs(graph, adj_node)

        self.finishing_order.append(node)
        self.finishing_time += 1

@@ -25,17 +25,28 @@
 ng, List
+, Set, Dict
 %0A
-
 %0A%0Aclass 
@@ -202,19 +202,25 @@
 ing_time
+: int
  = 
+-
 1%0A      
@@ -241,16 +241,27 @@
 ng_order
+: List%5Bint%5D
  = %5B%5D%0A  
@@ -279,16 +279,26 @@
 explored
+: Set%5Bint%5D
  = set(%5B
@@ -328,15 +328,18 @@
 node
- = None
+: int = -1
 %0A   
@@ -358,16 +358,38 @@
 mponents
+: Dict%5Bint, List%5Bint%5D%5D
  = %7B%7D%0A%0A 
@@ -497,16 +497,38 @@
 ed_graph
+: Dict%5Bint, List%5Bint%5D%5D
  = %7B%7D%0A  
@@ -904,16 +904,21 @@
 t%5D%5D) -%3E 
+List%5B
 List%5Bint
@@ -918,16 +918,17 @@
 ist%5Bint%5D
+%5D
 :%0A      
@@ -1668,16 +1668,21 @@
   res = 
+list(
 self.com
@@ -1697,16 +1697,17 @@
 values()
+)
 %0A       
@@ -1879,38 +1879,40 @@
  1. Updates the 
-global
+instance
  variable finish
@@ -1990,14 +1990,16 @@
 the 
-global
+instance
  var

update type hints after mypy run