<commit_before>import unittest
import utils


def mark_cycle(graph, in_cycle, visited, in_stack, curr):
    if in_cycle[curr]:
        return True

    if in_stack[curr]:
        in_cycle[curr] = True
        return True

    if visited[curr]:
        return False

    visited[curr] = True
    in_stack[curr] = True

    for outgoing in graph[curr]:
        if mark_cycle(graph, in_cycle, visited, in_stack, outgoing):
            in_cycle[curr] = True

    in_stack[curr] = False
    return in_cycle[curr]


class Solution(object):
    def eventualSafeNodes(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[int]
        """
        in_cycle = [False] * len(graph)
        visited = [False] * len(graph)
        in_stack = [False] * len(graph)

        for curr in xrange(len(graph)):
            if not visited[curr]:
                mark_cycle(graph, in_cycle, visited, in_stack, curr)

        return [i for i in xrange(len(graph)) if not in_cycle[i]]


class Test(unittest.TestCase):
    def test(self):
        cases = utils.load_json_from_path('../leetcode_test_cases/p802.json').test_cases

        for case in cases:
            actual = Solution().eventualSafeNodes(case.graph)
            self.assertEqual(case.expected, actual)
<commit_msg>802. Find Eventual Safe States<commit_after>import unittest
import utils

_NOT_VISITED = 0
_SAFE = 1
_UNSAFE = 2


# O(V+E) time. O(diameter) space. DFS.
class Solution(object):
    def eventualSafeNodes(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[int]
        """
        states = [_NOT_VISITED] * len(graph)

        def is_safe(node):
            if states[node] != _NOT_VISITED:
                return states[node] == _SAFE

            states[node] = _UNSAFE

            for outgoing in graph[node]:
                if not is_safe(outgoing):
                    return False

            states[node] = _SAFE
            return True

        for i in xrange(len(graph)):
            if states[i] == _NOT_VISITED:
                is_safe(i)

        return [i for i in xrange(len(graph)) if states[i] == _SAFE]


class Test(unittest.TestCase):
    def test(self):
        cases = utils.load_json_from_path('../leetcode_test_cases/p802.json').test_cases

        for case in cases:
            actual = Solution().eventualSafeNodes(case.graph)
            self.assertEqual(case.expected, actual)

{'fraction_non_alphanumeric': 0.10877626699629171, 'fraction_numerical': 0.004944375772558714, 'mean_word_length': 2.220159151193634, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, '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': '1417343', 'n_tokens_mistral': 785, 'n_tokens_neox': 748, 'n_words': 184}