【AtCoder】ARC111D：Orientation（600点） - たまごたまごのブログ

強連結な有向グラフの作り方がわからなかったので、備忘録として。

問題

前提知識

Lowlink

問題の概要

$N\$ 頂点 $\ M\$ 辺の単純な無向グラフ $\ G\$ と正整数列 $\ c_1, c_2, \ldots ,c_N\$ が与えられる。
$G\$ の各頂点 $\ v_i\$ から到達できる頂点の数（ $v_i\$ 自身も含む）が、ちょうど $\ c_i\$ になるように各辺に向き付けせよ。

制約

$\ 1\leq N\leq 100\$
$\ 0\leq M\leq\frac{N(N-1)}{2}\$
$\ 1\leq c_i\leq N\$
与えられるグラフに自己ループや多重辺は存在しない（非連結はあり得る）
与えられる入力には必ず解が存在する

解法

問題の言い換え

$G\$ 内の辺 $\ (u, v)\$ を適当にとってみます。

実は、 $c_u\$ と $\ c_v\$ が一致していなければ、即座に向き付け可能です。
もし $\ c_u > c_v\$ ならば、明らかに辺の向きは $\ u \rightarrow v\$ とするしかありません。 $u \leftarrow v\$ とした場合、 $u\$ から辿れる頂点は $\ v\$ からも辿れるため、 $c_u \leq c_v\$ となってしまうためです。

一方で、 $c_u = c_v\$ の場合には、 $u\$ と $\ v\$ は相互に到達できる必要があります。
この条件が $\ c_u = c_v\$ を満たす任意の辺 $\ (u, v)\$ について成立している必要があることから、結局以下の問題が解ければよいです。

$G\$ から $c_u\ = c_v\$ を満たす辺 $\ (u, v)\$ のみを取り出したグラフ $\ G'\$ を新たに $\ H\$ とする。
$G'\$ の各連結成分 $\ H\$ に対して、相互に到達可能（＝強連結）になるように向き付けせよ。
（ただし、問題の制約上、強連結になるように向き付けできることが保証されている。）

強連結なグラフの作り方

結論から言うと、強連結にできることが保証されている任意のグラフに対して、以下の操作で構築可能です。

連結グラフの頂点を一つ選び（ $v\$ とする）、 $v\$ からDFSを行い、通過した頂点と辺のみを使った根付き木（DFS木）を作る。DFS木上の辺を「根→葉」、それ以外の辺（後退辺）を「葉→根」となるようにグラフに向き付けを行うと、この連結成分は強連結になっている。

公式解説では詳細な証明は省略されていたので、上記操作で構築できることの証明を以下で行います。

操作の証明

方針

橋が存在するグラフは、明らかに強連結にできないことに注目します。つまり、今回与えられるグラフ $\ H\$ には橋が存在しません。

上記操作後のグラフが強連結でないと仮定した場合、 $H\$ には橋が存在する

ということを証明することで、橋が存在しない $\ H\$ においては、操作により必ず強連結にできることを証明します。

本体

まず、適当な頂点を根として選び、これを $\ 0\$ とします。
$0\$ を始点としてDFSを行うことでDFS木を作り、辿った順番に頂点に番号をつけます。さらに、先程の操作の説明通り、DFS木上の辺を「根→葉」、後退辺を「葉→根」となるようにグラフに向き付けを行います。

ここで、Lowlinkという概念を導入します。詳細は省略しますが、定義は以下のとおりです。
なお、先程つけた頂点番号は $\ ord\$ と一致します。

$ord[ v ] = \$ 頂点 $\ v \$ に初めて到達した時刻
$low[ v ] = \min \{ ord [ u ]\ |\ u:\$ 頂点 $\ v\$ からDFS木上の辺を葉方向に0回以上、後退辺を高々1回以下辿って到達できる頂点 $\} \$

↓こんな感じ

f:id:tmg_dayo:20220109140736p:plain

さて、操作後のグラフが強連結でないと仮定します。すると仮定より、ある頂点 $\ w\$ から頂点 $\ 0\$ には辿り着けないことがわかります。
（証明：DFS木の定義上、頂点 $\ 0\$ からは任意の頂点に辿り着けることから、任意の頂点から頂点 $\ 0\$ に辿り着けたら自動的に強連結になってしまうため。）

このとき、ある頂点 $\ v\$ について、 $low[v] = v\$ が成立します。
（証明： $low\$ の定義より、 $v\$ から頂点番号 $\ low[v]\$ の頂点までは辿ることができるので、 $\ low[v] < v\$ となる場合はより番号が小さい頂点に到達できることになってしまい、これを繰り返すと最終的に $\ 0\$ に到達できてしまうため。）

また、DFS木の作り方から、ある頂点 $\ u(< v)\$ について、DFS木上の辺 $\ u \rightarrow v\$ が存在します。

この辺について $\ ord[u] < low[v]\$ が成立していますが、
この式が成立しているとき、 $H\$ 上の辺 $\ (u, v)\$ は橋になっているという有名な事実があります。
（「橋　列挙　アルゴリズム」などで検索すると色々出てきます。こちらなど→グラフ探索アルゴリズムとその応用）

よって、「上記操作で強連結にできない→橋が存在する」が証明できたため、この操作でうまくいくことが示されました。

コード（Python3）

提出コード（Python3：54ms）

def main():
    # 入力
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in [0]*M]
    C = list(map(int, input().split()))
    # 隣接グラフGの構築
    G = [[] for _ in [0]*N]
    for a, b in AB:
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    # 辺に番号をつける
    edge = dict()
    for i in range(M):
        a, b = AB[i]
        edge[(a-1, b-1)] = i
    # 各頂点を始点にDFSを行い、両端のCが同じ辺のみを抽出、連結成分ごとに分解
    # 両端のCが異なる辺は即座に向き付け可能
    ans = [None]*M  # 各頂点の向き
    visited = [False]*N  # 探索済みかどうか
    G2 = []  # 各連結成分を保存
    for s in range(N):
        if visited[s]:
            continue
        visited[s] = True
        stack = [s]  # 探索用スタック
        H = set()  # 連結成分の辺を保存、重複の可能性があるのでsetで
        while stack:
            u = stack.pop()
            for v in G[u]:
                # 決まらない場合
                if C[u] == C[v]:
                    # 辺を保存
                    H.add((u, v))
                    if not visited[v]:
                        stack.append(v)
                        visited[v] = True
                # 決まる場合
                elif C[u] > C[v]:
                    if (u, v) in edge.keys():
                        ans[edge[(u, v)]] = "->"
                    else:
                        ans[edge[(v, u)]] = "<-"
                else:
                    if (u, v) in edge.keys():
                        ans[edge[(u, v)]] = "<-"
                    else:
                        ans[edge[(v, u)]] = "->"
        if H:
            # リストに直して格納
            G2.append(list(H))
    # 各連結成分について、DFSを行い木を作る
    edge_count = [0]*N  # 何番目の辺まで見たか
    for H in G2:
        # Hは隣接グラフになっていないので、隣接グラフH_graphを作る
        H_graph = [[] for _ in [0]*N]
        for u, v in H:
            H_graph[u].append(v)
            H_graph[v].append(u)
        root = H[0][0]  # 適当な頂点を根とする
        dist = [-1]*N  # 根からの距離
        dist[0] = 0
        stack = [root]
        # DFSを行う
        while stack:
            u = stack[-1]
            # 全ての辺を見終わっていた場合
            if edge_count[u] >= len(H_graph[u]):
                stack.pop()
                continue
            # 次の探索先を選ぶ
            v = H_graph[u][edge_count[u]]
            edge_count[u] += 1
            # 探索先が未訪問だった場合
            if edge_count[v] == 0:
                visited[v] = True
                dist[v] = len(stack)
                stack.append(v)
                # DFS木の根方向から葉方向に向き付け
                if (u, v) in edge.keys():
                    ans[edge[(u, v)]] = "->"
                else:
                    ans[edge[(v, u)]] = "<-"
        # 後退辺は根方向に向き付け
        for u, v in H:
            if (u, v) not in edge.keys():
                v, u = u, v
            # 向き付け済みの場合はスルー
            if ans[edge[(u, v)]] is not None:
                continue
            if dist[u] > dist[v]:
                ans[edge[(u, v)]] = "->"
            else:
                ans[edge[(u, v)]] = "<-"
    # 出力
    for elm in ans:
        print(elm)
main()