https://kntychance.hatenablog.jp/entry/2022/09/16/161858

この記事でやること

グラフの橋、関節点、二重辺連結成分、二重頂点連結成分といった概念と、それらを求める際に用いる「lowlink」という手法を解説します。

注意事項

この記事で扱うグラフは、全て単純な連結無向グラフとします。
ソースコードは全てPython3.8を用いております。コピペはご自由にどうぞ。（AtCoder等で使用する際はPyPy3で提出して問題ありません。）

モチベーション

グラフが与えられたときに、ある2頂点についてそれら結ぶ互いに素な（同じ辺/頂点を通らない）2つ以上のパスが存在するか？という問題を考えます。

これはグラフの二重連結性に関する問題と言えますね。

この問題の場合は最大フローで解けそうですが、もっと複雑な問題になってくると計算量が壊れてしまいます。そこで、特に二重連結性に関する問題を効率よく解く手段が欲しいわけですね。

lowlinkの基本

前提：DFS木と後退辺・横断辺

lowlinkの話に入る前に、知っておく必要のある用語と命題について解説します。

DFS木

グラフにおいて適当な頂点 $s$ を始点としてDFS（深さ優先探索）したとき、使用した辺を取ることで構成される、 $s$ を根とする木。特にこの記事では、DFS木上の各辺を葉方向の有向辺とします。

後退辺

グラフから全域木 $T$ を取ります。このとき使われなかった辺 $\{u, v\}$ について、 $u$ と $v$ が $T$ における祖先と子孫の関係にあるとき、後退辺といいます。

横断辺

グラフから全域木を取ります。このとき使われなかった辺のうち後退辺でないものを横断辺といいます。

命題：グラフからDFS木を取ったとき、使われなかった辺は全て後退辺となる

証明

背理法で示します。

DFS木 $T$ について、横断辺 $\{u, v\}$ が存在すると仮定します。

また、DFSにおける各頂点 $i$ の行きがけ順(pre-order)を $\text{ord}[i]$ で表すとします。

一般性を失わず、 $\text{ord}[u] \lt \text{ord}[v]$ とします。

$\{u, v\}$ は横断辺であることから、 $v$ に訪れるのは $u$ から帰ったあとであるはずです。

つまり、任意の $u$ の隣接点 $w \in \text{adj}[u]$ について、 $\text{ord}[u] \gt \text{ord}[w]$ が成り立ちます。

ここで、 $v \in \text{adj}[u]$ より $\text{ord}[u] \gt \text{ord}[v]$ となり、矛盾　☐

ちなみに、全ての使われていない辺が後退辺となる全域木はDFS木ですが、実は全て横断辺となる全域木も存在します。どんな木でしょう？

参考↓

atcoder.jp

lowlinkでやること

ordの定義

先ほどの証明で使った定義通り、DFSにおける各頂点 $i$ の行きがけ順(pre-order)を $\text{ord}[i]$ で表すとします。

lowの定義

DFSによって $\text{ord}$ と、以下で定義される $\text{low}$ を求めておきます：

$\text{low}[i] :=$ 頂点 $i$ から後退辺を高々 $1$ 回まで使って到達できる頂点の集合 $L[i]$ について、 $\underset{j \in L[i]}{\text{min}}\{\text{ord}[j]\}$

例です。定義と照らし合わせて確認してみてください。

この $\text{ord}$ と $\text{low}$ を用いて、二重連結性に関するアレコレを求めていく手法をlowlinkといいます。

ordとlowの求め方

まずDFSをしながら $\text{ord}$ を埋めていき、 $\text{low}$ もその値で初期化します。その最中に後退辺 $(u, v)$ が見つかれば、 $\text{low}[u]$ を $\text{ord}[v]$ でchmin*1します。

次に、ボトムアップ順に各頂点 $u$ について、 $\text{low}[u]$ を各 $u$ の子 $v \in \text{son}[u]$ について $\text{low}[v]$ でchminしていくことで、 $\text{low}$ を求めることができます。

実装例

下記の実装例では、DFSをするついでに各頂点の子を表す二重配列 $\text{son}$ 、頂点のトポロジカルソート順を表す配列 $\text{tps}$ の作成を行っています。

計算量は $O(N+M)$

class LowLink():
    def __init__(self, adj):
        self.n = len(adj)
        self.ord = [None]*self.n
        self.low = [None]*self.n
        self.son = [[] for _ in range(self.n)] # son[i] := 頂点iの子を格納したlist
        self.back_edge = [[] for _ in range(N)] # back_edge[i] := 頂点iから出る後退辺の終点を格納したlist
        self.tps = [] # 頂点のトポロジカルソート

        # DFSでord, son, tpsを求め、lowを初期化
        t = 0 # 今までに訪れた頂点数
        stack = [(None, 0)] # 直前にいた頂点, 今いる頂点
        while stack: 
            pre, now = stack.pop()
            if self.ord[now] is not None: # 直前に通った辺が後退辺ならば
                if self.ord[pre] < self.ord[now]: continue # 後退辺を根側から進んでいた場合は無視
                self.low[pre] = min(self.low[pre], self.ord[now]) # low[pre]をord[now]でchmin
                self.back_edge[pre].append(now)
                continue
            if pre is not None:
                self.son[pre].append(now)
            self.tps.append(now)
            self.ord[now] = t # 行きがけ順を書き込む
            self.low[now] = self.ord[now] # low[now]をord[now]で初期化
            t += 1
            for next in adj[now]:
                if next == pre: continue
                stack.append((now, next))
        
        # ボトムアップ順にchminしてlowを求める
        for u in reversed(self.tps[1:]):
            for v in self.son[u]:
                self.low[u] = min(self.low[u], self.low[v])

lowlinkの活用例

ここからは、先ほど求めた $\text{ord}$ と $\text{low}$ を用いて、二重連結性に関するアレコレを求める方法を解説していきます。

橋と二重辺連結成分

橋(bridge)

削除するとグラフが連結でなくなるような辺。

どの閉路にも含まれない辺とも言い換えられます。

現実ネットワークで考えると「断線したらヤバい辺」にあたります。

二重辺連結成分(two-edge connected component)

グラフから橋を全て削除したときの連結成分。

任意の異なる2つの二重辺連結成分 $A, B$ について、以下の性質が成り立ちます。

任意の異なる2頂点 $a_1, a_2 \in A$ について、辺について互いに素なパス $a_1 - a_2$ が少なくとも2つ存在する
任意の2頂点 $a \in A, b \in B$ について、辺について互いに素なパス $a - b$ を2つ以上取ることはできない

二重連結成分分解の方法

グラフから橋と二重辺連結成分を列挙する方法を考えます。

適当な頂点からDFSして $\text{ord}$ と $\text{low}$ を求めておきましょう。

橋の判定

後退辺は明らかに橋ではないので、木上の辺のみ見ていきます。

辺 $(u, v)$ が閉路に含まれる

$\Leftrightarrow$ $v$ から後退辺を高々 $1$ 回まで使って $u$ または $u$ の祖先に到達できる

より、閉路に含まれない、すなわち橋であるための必要十分条件は

辺 $(u, v)$ が橋である

$\Leftrightarrow \text{low}[v] \gt \text{ord}[u]$

となります。

緑の辺が橋。 $\text{low}[v] \gt \text{ord}[u]$ となっている

緑の辺が橋。 $\text{low}[v] \gt \text{ord}[u]$ となっている

二重辺連結成分の列挙

橋を通らないようにDFSして連結成分を求めていけばいいですね。

例えば頂点 $0$ からスタートすると、 $0, 1, 2, 5, 6, 8, 9$ と連結成分が求まる

実装例

各連結成分の頂点集合を二重配列で持つ $\text{tecc}$ 、元グラフの頂点から連結成分を逆引きするための配列 $\text{tecc_idx}$ を求めたいです。

根から始め、橋があれば「その先の頂点を始点としてまたDFSしますよー」というフラグを追加する、という感じの方針で実装します。

二重連結成分分解のついでに、連結成分を1点に縮約することで得られる、連結成分を頂点、橋を辺とした木を構築します。

（この木を作っておくことで、一般的に木で扱えるような色々なテクニックを用いて問題を効率よく解けたりします。）

この木を表現するために隣接リスト $\text{tecc_tree}$ も追加で作ります。

計算量は $O(N)$

    # 二重辺連結成分分解
    def two_edge_connected_component(self):
        tecc = [] # tecc[i] := 連結成分iに属する頂点の番号を格納したlist
        tecc_idx = [None]*self.n # tecc_idx[i] := 頂点iが属する連結成分の番号(上記teccにおけるindexに対応)
        tecc_tree = [] # 連結成分を頂点、橋を辺としたグラフ(木)の隣接リスト
        sub_roots = [(None, 0)] # 橋を見つけるごとに、その先は部分木として別にDFSしなおす。
        idx = 0 # 今いる頂点の連結成分の番号
        while sub_roots:
            stack = [sub_roots.pop()] # 部分木の根からDFS
            tecc.append([]) # 今いる頂点の連結成分を格納するlistを追加
            tecc_tree.append([]) # 今いる頂点の連結成分の隣接先を格納するlistを追加
            while stack:
                pre, now = stack.pop()
                tecc[idx].append(now) # 今いる頂点を連結成分idxに追加
                tecc_idx[now] = idx # 今いる頂点の連結成分の番号idxを記録
                if pre is not None and idx != tecc_idx[pre]: # 直前に橋を通ってきていたら
                    tecc_tree[idx].append(tecc_idx[pre]) # その橋で繋がれた2つの連結成分を辺で結ぶ
                    tecc_tree[tecc_idx[pre]].append(idx)
                for next in self.son[now]:
                    if self.low[next] > self.ord[now]: # 橋なら
                        sub_roots.append((now, next)) # その先は別の連結成分
                    else: # そうでないなら
                        stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
            idx += 1
        return tecc, tecc_idx, tecc_tree

例題

atcoder.jp

解説

二重辺連結成分分解して縮約した木を考えます。この木上の辺は全て橋なので、異なる2頂点間を結ぶパスで、辺について素なものは高々1つしか取れません。よって、（ $A, B, C$ を木上の対応する頂点で置きなおしたとして） $A \rightarrow B \rightarrow C$ というトレイルで同じ辺を通らないためには $B$ が $A-C$ パス上に存在することが必要十分条件となります。

この判定方法は色々考えられますが、私の提出コードではオイラーツアー*2を使用しました。

二重辺連結成分分解し縮約した木上で、A-Cパス上にBが存在するかを判定すればよい

ACコード

Submission #34875923 - AtCoder Regular Contest 039

関節点と二重頂点連結成分

関節点(articulation point)

削除するとグラフが連結でなくなるような頂点。

現実ネットワークで考えると「ダウンしたらやばい中継点」にあたります。

二重頂点連結成分(biconnected component)

頂点の部分集合 $A \subset V$ が二重頂点連結成分である

$\underset{\text{def}}{\Leftrightarrow}$ 任意の頂点 $a \in A$ について、 $A \setminus \{a\}$ は連結であり、かつ $A$ は極大である

最後の「極大である」というのは、前半の二重頂点連結性に関する条件を満たす $A^\prime, A$ について $A^\prime \subset A$ なら $A$ の方を二重頂点連結成分としますよー、という意味です。

この定義から、関節点は複数の二重頂点連結成分に属する場合もあることに注意してください。

二重頂点連結成分分解の方法

グラフから関節点と二重頂点連結成分を列挙する方法を考えます。

適当な頂点からDFSして $\text{ord}$ と $\text{low}$ を求めておきましょう。

関節点の判定

関節点を考える上で重要なのは「”どの頂点に対して”関節点なのか」という点。

まず、根について考えます。

少し観察すれば直ちに下の事実が得られるはずです。

根 $r$ が子 $v$ に対して関節点

$\Leftrightarrow$ 根 $r$ の出次数が $2$ 以上

次に、根以外の頂点について考えます。

DFS木上で根以外のある頂点を削除したとき、それによって根側から分離される頂点はどれか？を見る必要があります。

では、頂点 $u$ を削除した際に子 $v$ が分離されるとはどういうときでしょうか？

橋を列挙したときと同様に考えると、 $v$ から $u$ の祖先である頂点に後退辺を高々1つだけ到達できれば分離されないことになるので

根でない頂点 $u$ が子 $v$ に対して関節点

$\Leftrightarrow \text{low}[v] \ge \text{ord}[u]$

となります。

$\text{low}[v] \ge \text{ord}[u]$ のとき、 $u$ は $v$ に対して関節点となる

$\text{low}[v] \ge \text{ord}[u]$ のとき、 $u$ は $v$ に対して関節点となる

二重頂点連結成分の列挙

二重頂点連結成分は辺集合で見ると重複無しに分解できます。となると辺基準の分解しておくと嬉しい場合もある（かもしれない、要出典）ので、辺基準の分解と頂点基準の分解を両方行うことにします。

辺基準の分解で考えると、二重連結成分分解は「木上の、親側の端点を削除したら子側の端点が根から分離されてしまう辺」すなわち下図の緑の辺からスタートして、緑の辺を通らないようにDFSすることで実現できるとわかるでしょう。

例えば辺 $(1, 2)$ からスタートすると、 $(1, 2), (2, 5), (5, 1)$ と連結成分が求まる

例えば辺 $(1, 2)$ からスタートすると、 $(1, 2), (2, 5), (5, 1)$ と連結成分が求まる

頂点基準で分解する場合は、辺基準で分解中に通った頂点を順次記録していけばよいですね。

実装例

辺基準で分解した際の各連結成分の辺集合を二重配列で持つ $\text{bce}$ 、頂点基準で分解した際の各連結成分の頂点集合を二重配列で持つ $\text{bcv}$ 、各頂点が関節点であるかどうかを表すbool値配列 $\text{is_ap}$ を作っています。

二重辺連結成分分解と同様、根から始め、緑の辺があれば「その先の頂点を始点としてまたDFSしますよー」というフラグを追加する、という感じの方針で実装しました。

注意点として、DFSを開始するごとにそのパートの連結成分を格納する空listを用意していますが、根が関節点（出次数が2以上）の場合のみそのパートでは連結成分が構成されないという例外があるので、そのときは一時的に作ったlistをすぐにpop()しています。

計算量は $O(N+M)$

（ $\text{bce}$ を作らない、つまり、後退辺を無視するなら $O(N)$ ）

    # 二重頂点連結成分分解
    def biconnected_component(self):
        bce = [] # bce[i] := 連結成分iに属する辺を格納したlist
        bcv = [] # bcv[i] := 連結成分iに属する頂点を格納したlist
        is_ap = [False]*self.n # is_ap[i] := 頂点iは関節点であるか(True/False)
        sub_roots = [(None, 0)] #「ある子に対する関節点」を見つけるごとに、その子以降は部分木として別にDFSしなおす。
        idx = 0 # 今いる頂点の連結成分の番号
        while sub_roots:
            stack = [sub_roots.pop()] # 部分木の根からDFS
            bce.append([]) # 今いる頂点の連結成分に含まれる辺を格納するlistを追加
            bcv.append([]) # 今いる頂点の連結成分に含まれる頂点を格納するlistを追加
            if stack[0][0] is not None: # 直前に通った頂点(関節点)が存在するなら
                bcv[idx].append(stack[0][0]) # それを連結成分idxに追加
            while stack:
                pre, now = stack.pop()
                if pre is not None: # 直前に通った辺が存在するなら
                    bce[idx].append((pre, now)) # 通ってきた辺を連結成分idxに追加 
                bcv[idx].append(now) # 今いる頂点を連結成分idxに追加
                if now == 0: # 今いる頂点nowが根で
                    if len(self.son[now]) >= 2: # 関節点であるなら
                        for next in self.son[now]:
                            is_ap[now] = True # 関節点であことを記録
                            sub_roots.append((now, next)) # その先は別の連結成分
                        bce.pop() # 「根の関節点のみ」の連結成分は存在しないが追加してしまっているので、例外的に削除する
                        bcv.pop()
                        idx -= 1
                    else: # 関節点でないなら
                        for next in self.son[now]:
                            stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
                else: # 根でなく
                    for next in self.son[now]:
                        if self.low[next] >= self.ord[now]: # 子nextに対して関節点なら
                            is_ap[now] = True # 関節点であることを記録
                            sub_roots.append((now, next)) # その先は別の連結成分
                        else: # 関節点でないなら
                            stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
                if now == 0 and len(self.son[now]) <= 1:
                    for back in self.back_edge[now]: # 今いる頂点から出る後退辺は同じ連結成分なので
                        bce[idx].append((now, back)) # 連結成分idxに追加
            idx += 1
        return bce, bcv, is_ap

block-cut tree

二重辺連結成分分解では連結成分を縮約するだけで木が構築できました。では、二重頂点連結成分分解でも同様な「意味のある木」を構築したいです。

しかし、そのままだと関節点が複数の連結成分に共有されていて縮約は難しそうですね。そこで、「連結成分そのもの」を表す頂点を用意し、各関節点についてそれが含まれる連結成分を表す頂点を辺で結ぶことにします。

このようにして作られる木をblock-cut treeと呼ぶそうです。

実装例

データの表現方法としては、関節点の個数を $\text{num_ap}$ とおき、木上の頂点について関節点について順に $[0, \text{num_ap})$ の番号を割り振り、連結成分を表す頂点は $[\text{num_ap}, \text{木の頂点の個数})$ の番号を割り振って隣接リスト $\text{bc_tree}$ を作っています。

また、各木の頂点が持つ元グラフに関する頂点集合を

関節点 ⇒ それ1つの単元集合
連結成分を表す頂点 ⇒ 元の連結成分から関節点を除いた頂点集合（空集合になる可能性もある）

と定義して二重配列で持った $\text{bc}$ 、また元のグラフの頂点から木上の頂点を逆引きする配列 $\text{bc_idx}$ を作っています。

具体的な方法はコードで確認して頂きたいのですが、先ほど求めた $\text{bcv}$ と $\text{is_ap}$ を使うことで簡単に作れます。

計算量は $O(N+M)$

（ $\text{biconnected_component()}$ にて $\text{bce}$ を作らない、つまり、後退辺を無視するなら $O(N)$ ）

    # block-cut treeを構築
    def block_cut_tree(self):
        bce, bcv, is_ap = self.biconnected_component() # 二重頂点連結成分分解
        num_ap = sum(is_ap) # 関節点の個数
        bc = [[] for _ in range(num_ap+len(bcv))] 
        # bc[i] := block-cut tree上の頂点iに対応する頂点を格納したlist
        # [0:num_ap)は関節点に対応する頂点で、その関節点のみがlistに含まれる
        # [num_ap:len(bc))は連結成分に対応する頂点で、その連結成分から関節点を除いたものがlistに含まれる
        # block-cut tree上の頂点iが関節点に対応している ⇔ i < num_ap
        bc_idx = [None]*self.n
        # bc_idx[i] := (元グラフの)頂点iが属するblock-cut tree上の頂点の番号(bc, bc_treeのindexに対応)
        # 関節点でない頂点iについて、対応するbce, bcvのindexが知りたい場合、bc_idx[i]-num_apで取得可能。
        bc_tree = [[] for _ in range(num_ap+len(bcv))] # bc_tree[i] := block-cut tree上の頂点iの隣接頂点を格納したlist
        idx = 0 # 今見ているblock-cut tree上の頂点番号
        for v in range(self.n): # (元グラフの)各頂点vについて
            if is_ap[v]: # 関節点なら
                bc[idx].append(v) # block-cut tree上の頂点idxにvを対応させる
                bc_idx[v] = idx
                idx += 1
        for bcv_i in bcv: # 各連結成分の
            for v in bcv_i: # 各頂点vについて
                if is_ap[v]: # 関節点なら
                    bc_tree[idx].append(bc_idx[v]) # block-cut tree上の頂点idxと関節点vに対応した頂点を辺で結ぶ
                    bc_tree[bc_idx[v]].append(idx)
                else: # そうでないなら
                    bc[idx].append(v) # block-cut tree上の頂点idxに対応した頂点集合に頂点vを追加
                    bc_idx[v] = idx
            idx += 1
        return bc, bc_idx, bc_tree, num_ap, bce, bcv, is_ap

例題

atcoder.jp

解説

まず、以下のように $x$ 座標または $y$ 座標が等しい頂点を辺で結ぶことでグラフを構築します。

このグラフにおいてマッチングを考えるとき、頂点数が偶数の連結成分には完全マッチングが存在することが示せます。（証明は公式解説を参照してください。）

よって、この問題は各頂点を取り除いたときに全ての連結成分の頂点数が偶数になるかを判定する問題に帰着されます。

ここで、例えば全ての頂点の $x$ 座標が等しいようなケースで辺の本数が $O(N^2)$ となってしまい、扱うことができません。

そこで、「頂点を1つ取り除いたときの連結性を判定する」という問題の性質から三重以上の頂点連結成分は二重まで緩めても解に影響が出ないことを利用して、下図のように辺の本数を $O(N)$ に落とします。

また、全頂点数が奇数なので、頂点数が奇数の連結成分は少なくとも $1$ つ存在しますが、 $2$ つ以上存在する場合は明らかに $1$ つの頂点を削除するだけで全ての連結成分の頂点数を奇数にすることはできないので、頂点数が奇数の連結成分がただ $1$ つ存在する場合のみ考えます。

さらに、そのような場合において頂点数が偶数の連結成分から頂点を取り除くのも明らかに不適なので、ただ $1$ つの頂点数が奇数の連結成分にのみ着目します。

まず、「 $1$ 頂点を取り除いたときに連結でなくなるかどうか」が知りたいので、とりあえず二重頂点連結成分分解し、block-cut treeを作っておきましょう。

block-cut treeを構築。木の頂点 $i$ 内の数字は、 $\text{len}(\text{bc}[i])$ を表す

この連結成分において、関節点でない頂点を $1$ つ削除すると、連結性は崩れずに頂点数が $1$ 減るので、全ての連結成分の頂点数が偶数となります。では、関節点を取り除くとどうなるでしょうか？

これは実際に木から関節点を取り除いてみることですぐに結果がわかります。

すなわち、いくつかの部分木に分離するので、そのサイズの偶奇を確かめ、その中に $1$ つでも奇数のものがあれば不適、そうでないなら適切となります。

block-cut treeから関節点を $1$ つ削除すると、いくつかの部分木に分離する

あとは部分木のサイズが求まればよいので、根を適当に固定した木dpをすることで解くことができます。

以上より、全体 $O(N)$ で解けました。

ACコード

Submission #34866716 - AtCoder Regular Contest 045

（MLEとの戦いの結果、 $\text{bce}$ を求めないといったような実装例からの変更点が存在します。）

ソースコード全体

class LowLink():
    def __init__(self, adj):
        self.n = len(adj)
        self.ord = [None]*self.n
        self.low = [None]*self.n
        self.son = [[] for _ in range(self.n)] # son[i] := 頂点iの子を格納したlist
        self.back_edge = [[] for _ in range(N)] # back_edge[i] := 頂点iから出る後退辺の終点を格納したlist
        self.tps = [] # 頂点のトポロジカルソート

        # DFSでord, son, tpsを求め、lowを初期化
        t = 0 # 今までに訪れた頂点数
        stack = [(None, 0)] # 直前にいた頂点, 今いる頂点
        while stack: 
            pre, now = stack.pop()
            if self.ord[now] is not None: # 直前に通った辺が後退辺ならば
                if self.ord[pre] < self.ord[now]: continue # 後退辺を根側から進んでいた場合は無視
                self.low[pre] = min(self.low[pre], self.ord[now]) # low[pre]をord[now]でchmin
                self.back_edge[pre].append(now)
                continue
            if pre is not None:
                self.son[pre].append(now)
            self.tps.append(now)
            self.ord[now] = t # 行きがけ順を書き込む
            self.low[now] = self.ord[now] # low[now]をord[now]で初期化
            t += 1
            for next in adj[now]:
                if next == pre: continue
                stack.append((now, next))
        
        # ボトムアップ順にchminしてlowを求める
        for u in reversed(self.tps[1:]):
            for v in self.son[u]:
                self.low[u] = min(self.low[u], self.low[v])

    # 二重辺連結成分分解
    def two_edge_connected_component(self):
        tecc = [] # tecc[i] := 連結成分iに属する頂点の番号を格納したlist
        tecc_idx = [None]*self.n # tecc_idx[i] := 頂点iが属する連結成分の番号(上記teccにおけるindexに対応)
        tecc_tree = [] # 連結成分を頂点、橋を辺としたグラフ(木)の隣接リスト
        sub_roots = [(None, 0)] # 橋を見つけるごとに、その先は部分木として別にDFSしなおす。
        idx = 0 # 今いる頂点の連結成分の番号
        while sub_roots:
            stack = [sub_roots.pop()] # 部分木の根からDFS
            tecc.append([]) # 今いる頂点の連結成分を格納するlistを追加
            tecc_tree.append([]) # 今いる頂点の連結成分の隣接先を格納するlistを追加
            while stack:
                pre, now = stack.pop()
                tecc[idx].append(now) # 今いる頂点を連結成分idxに追加
                tecc_idx[now] = idx # 今いる頂点の連結成分の番号idxを記録
                if pre is not None and idx != tecc_idx[pre]: # 直前に橋を通ってきていたら
                    tecc_tree[idx].append(tecc_idx[pre]) # その橋で繋がれた2つの連結成分を辺で結ぶ
                    tecc_tree[tecc_idx[pre]].append(idx)
                for next in self.son[now]:
                    if self.low[next] > self.ord[now]: # 橋なら
                        sub_roots.append((now, next)) # その先は別の連結成分
                    else: # そうでないなら
                        stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
            idx += 1
        return tecc, tecc_idx, tecc_tree
    
    # 二重頂点連結成分分解
    def biconnected_component(self):
        bce = [] # bce[i] := 連結成分iに属する辺を格納したlist
        bcv = [] # bcv[i] := 連結成分iに属する頂点を格納したlist
        is_ap = [False]*self.n # is_ap[i] := 頂点iは関節点であるか(True/False)
        sub_roots = [(None, 0)] #「ある子に対する関節点」を見つけるごとに、その子以降は部分木として別にDFSしなおす。
        idx = 0 # 今いる頂点の連結成分の番号
        while sub_roots:
            stack = [sub_roots.pop()] # 部分木の根からDFS
            bce.append([]) # 今いる頂点の連結成分に含まれる辺を格納するlistを追加
            bcv.append([]) # 今いる頂点の連結成分に含まれる頂点を格納するlistを追加
            if stack[0][0] is not None: # 直前に通った頂点(関節点)が存在するなら
                bcv[idx].append(stack[0][0]) # それを連結成分idxに追加
            while stack:
                pre, now = stack.pop()
                if pre is not None: # 直前に通った辺が存在するなら
                    bce[idx].append((pre, now)) # 通ってきた辺を連結成分idxに追加 
                bcv[idx].append(now) # 今いる頂点を連結成分idxに追加
                if now == 0: # 今いる頂点nowが根で
                    if len(self.son[now]) >= 2: # 関節点であるなら
                        for next in self.son[now]:
                            is_ap[now] = True # 関節点であことを記録
                            sub_roots.append((now, next)) # その先は別の連結成分
                        bce.pop() # 「根の関節点のみ」の連結成分は存在しないが追加してしまっているので、例外的に削除する
                        bcv.pop()
                        idx -= 1
                    else: # 関節点でないなら
                        for next in self.son[now]:
                            stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
                else: # 根でなく
                    for next in self.son[now]:
                        if self.low[next] >= self.ord[now]: # 子nextに対して関節点なら
                            is_ap[now] = True # 関節点であることを記録
                            sub_roots.append((now, next)) # その先は別の連結成分
                        else: # 関節点でないなら
                            stack.append((now, next)) # その先は同じ連結成分なのでDFSを続ける
                if now == 0 and len(self.son[now]) <= 1:
                    for back in self.back_edge[now]: # 今いる頂点から出る後退辺は同じ連結成分なので
                        bce[idx].append((now, back)) # 連結成分idxに追加
            idx += 1
        return bce, bcv, is_ap
    
    # block-cut treeを構築
    def block_cut_tree(self):
        bce, bcv, is_ap = self.biconnected_component() # 二重頂点連結成分分解
        num_ap = sum(is_ap) # 関節点の個数
        bc = [[] for _ in range(num_ap+len(bcv))] 
        # bc[i] := block-cut tree上の頂点iに対応する頂点を格納したlist
        # [0:num_ap)は関節点に対応する頂点で、その関節点のみがlistに含まれる
        # [num_ap:len(bc))は連結成分に対応する頂点で、その連結成分から関節点を除いたものがlistに含まれる
        # block-cut tree上の頂点iが関節点に対応している ⇔ i < num_ap
        bc_idx = [None]*self.n
        # bc_idx[i] := (元グラフの)頂点iが属するblock-cut tree上の頂点の番号(bc, bc_treeのindexに対応)
        # 関節点でない頂点iについて、対応するbce, bcvのindexが知りたい場合、bc_idx[i]-num_apで取得可能。
        bc_tree = [[] for _ in range(num_ap+len(bcv))] # bc_tree[i] := block-cut tree上の頂点iの隣接頂点を格納したlist
        idx = 0 # 今見ているblock-cut tree上の頂点番号
        for v in range(self.n): # (元グラフの)各頂点vについて
            if is_ap[v]: # 関節点なら
                bc[idx].append(v) # block-cut tree上の頂点idxにvを対応させる
                bc_idx[v] = idx
                idx += 1
        for bcv_i in bcv: # 各連結成分の
            for v in bcv_i: # 各頂点vについて
                if is_ap[v]: # 関節点なら
                    bc_tree[idx].append(bc_idx[v]) # block-cut tree上の頂点idxと関節点vに対応した頂点を辺で結ぶ
                    bc_tree[bc_idx[v]].append(idx)
                else: # そうでないなら
                    bc[idx].append(v) # block-cut tree上の頂点idxに対応した頂点集合に頂点vを追加
                    bc_idx[v] = idx
            idx += 1
        return bc, bc_idx, bc_tree, num_ap, bce, bcv, is_ap