サイクル検出
(Graph/misc/cycle_detection.py)

• View this file on GitHub
• Last update: 2021-01-14 17:41:58+09:00

Verified with

• TestCase/AOJ/GRL_4_A.test.py
• TestCase/LibraryChecker/cycle_detection.test.py

Code

def cycle_detection(graph):
    def _dfs(v):
        stack = [v, 0]
        visited[v] = 1
        while stack:
            v, idx = stack[-2:]
            if idx < len(graph[v]):
                nxt_v = graph[v][idx]
                stack[-1] += 1
                if visited[nxt_v] == 1:
                    # detect cycle
                    cycle.append(nxt_v)
                    while cycle[0] != v:
                        cycle.append(v)
                        stack.pop(), stack.pop()
                        v = stack[-2]
                    cycle.reverse()
                    return
                if visited[nxt_v] == 2:
                    continue
                visited[nxt_v] = 1
                stack.append(nxt_v)
                stack.append(0)
            else:
                visited[v] = 2
                stack.pop(), stack.pop()

    n = len(graph)
    visited = [0] * n
    cycle = []
    for v in range(n):
        if not cycle and visited[v] == 0:
            _dfs(v)
    return cycle

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page