<commit_before>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
<commit_msg>update type hints after mypy run<commit_after>from typing import Mapping, List, Set, Dict


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

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

    def reverse_graph(self, graph: Mapping[int, List[int]]) -> Mapping[int, List[int]]:
        reversed_graph: Dict[int, List[int]] = {}
        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[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 = list(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 instance variable finishing_order with order each node finished processing.
        2. Updates the instance 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

{'fraction_non_alphanumeric': 0.08489795918367347, 'fraction_numerical': 0.001836734693877551, 'mean_word_length': 2.1416666666666666, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3943240', 'n_tokens_mistral': 1389, 'n_tokens_neox': 1338, 'n_words': 391}