二重連結性とlowlinkの話

 

この記事でやること

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

 

注意事項

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

 

モチベーション

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

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

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

 

lowlinkの基本

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

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

DFS木

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

後退辺

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

横断辺

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

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

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}

この \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]となっている

 

二重辺連結成分の列挙

橋を通らないように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以上

根の出次数が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に対して関節点となる

 

二重頂点連結成分の列挙

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

辺集合で見ると、各連結成分は互いに独立している

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

例えば辺 (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と呼ぶそうです。

グラフを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座標または 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

 

類題

https://onlinejudge.u-aizu.ac.jp/problems/3022

H - Tourist on Graph

 

参考資料

lowlink

グラフにおける橋(bridge)を検出するアルゴリズム | アルゴリズムロジック

Biconnected component - Wikipedia

https://web.iitd.ac.in/~bspanda/biconnectedMTL776.pdf

オイラーツアー

オイラーツアーした木に対するクエリ - Qiita

Euler Tour のお勉強 | maspyのHP

*1: xをyで\text{chmin} \underset{\text{def}}{\Leftrightarrow} x \leftarrow \text{min}\{x, y\}

*2:オイラーツアーについて知りたい方は、参考資料に私が勉強する際に参考にさせて頂いた記事のリンクを掲載しておりますので、そちらを参照していただければと思います。