有向グラフのDFS木の構築
(Graph/misc/DigraphDFSTree.py)

• View this file on GitHub
• Last update: 2021-01-25 23:26:41+09:00

Verified with

• TestCase/AOJ/ALDS1_11_B.test.py

Code

class DigraphDFSTree:
    def __init__(self, n):
        self.n = n
        self.digraph = [[] for _ in range(n)]
        self.dfstree = [[] for _ in range(n)]
        self.par = [-1] * n
        self.arrival = [-1] * n
        self.depature = [-1] * n
        self.roots = set()

    def add_edge(self, v, nxt_v):
        self.digraph[v].append(nxt_v)

    def build(self, root=None):
        k = 0
        idxs = [0] * self.n
        if root is not None:
            self.roots.add(v)
            self._dfs(v, idxs, k)
        else:
            for v in range(self.n):
                if self.arrival[v] == -1:
                    self.roots.add(v)
                    k = self._dfs(v, idxs, k)

    def _dfs(self, root, idxs, k):
        stack = [root]
        while stack:
            v = stack[-1]
            idx = idxs[v]
            if self.arrival[v] == -1:
                self.arrival[v] = k
                k += 1
            if idx < len(self.digraph[v]):
                nxt_v = self.digraph[v][idx]
                idxs[v] += 1
                if self.arrival[nxt_v] == -1:
                    self.dfstree[v].append(nxt_v)
                    self.par[nxt_v] = v
                    stack.append(nxt_v)
            else:
                self.depature[v] = k
                k += 1
                stack.pop()
        return k

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