二重辺連結成分分解
(Graph/Decomposition/TwoEdgeConnectedComponents.py)

• View this file on GitHub
• Last update: 2021-01-28 21:03:43+09:00

概要

無向グラフを二重辺連結成分分解するアルゴリズム。

使い方

TwoEdgeConnectedComponents(n: int)
頂点数 n の辺のないグラフを構築する。計算量 $O(V)$

• add_edge(u: int, v: int) -> None
  頂点 u と頂点 v との間に無向辺を追加する。計算量 $O(1)$

• build() -> None
  二重辺連結成分分解を行う。build の実行後には、インスタンス変数である labels に各頂点の二重辺連結成分の番号が格納される。計算量 $O(V + E)$

• groups() -> List[List[int]]
  二重辺連結成分ごとに元の頂点を列挙する。計算量 $O(V)$

Depends on

• 関節点・橋の列挙、DFS 木の構築 (Low Link) (Graph/misc/LowLink.py)

Verified with

• TestCase/LibraryChecker/two_edge_connected_components.test.py

Code

from Graph.misc.LowLink import LowLink


class TwoEdgeConnectedComponents(LowLink):
    def build(self):
        super().build()
        self.labels = [-1] * self.n
        self.lb_cnt = 0
        for v in range(self.n):
            if self.labels[v] != -1:
                continue
            self.labels[v] = self.lb_cnt
            stack = [v]
            while stack:
                v = stack.pop()
                for nxt_v in self.graph[v]:
                    if self.ord[v] < self.low[nxt_v] or self.ord[nxt_v] < self.low[v]:
                        continue
                    if self.labels[nxt_v] != -1:
                        continue
                    self.labels[nxt_v] = self.lb_cnt
                    stack.append(nxt_v)
            self.lb_cnt += 1

    def groups(self):
        res = [[] for _ in range(self.lb_cnt)]
        for v, lb in enumerate(self.labels):
            res[lb].append(v)
        return res

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