lib.graph package

Submodules

lib.graph.euler_tour module

オイラーツアー

class lib.graph.euler_tour.EulerTour(n: int)

ベースクラス: object

add_edge(u: int, v: int): 辺 {u,v} を追加する

build(root: int): root を根として順序付けを行う

get_id(v: int) → tuple[int, int]: 頂点 v の (行きがけ順, 帰りがけ順) の番号を返す

lib.graph.low_link module

lib.graph.sccd module

強連結成分分解

class lib.graph.sccd.SCC(n: int)

ベースクラス: object

DAG: list[list[int]] | None: 構成されたDAG

G: list[list[int]]: グラフ

add_edge(u: int, v: int): グラフに辺 (u,v) を追加する

belong: list[list[int]] | None: 頂点 i がどのグループに所属しているか

components: list[int] | None: 強連結成分の集合

decompose(): 強連結成分分解を行う

group_count: int | None: 強連結成分の数

n: 頂点数

rG: list[list[int]]: 辺の向きを反転させたグラフ

Module contents