🌿

ABC266 F - Well-defined Path Queries on a Namori Python解答例

2022/08/28に公開

Python

AtCoder Beginner Contest 266 F - Well-defined Path Queries on a NamoriをPythonで解きます。

問題

問題文をAtCoderのページより引用します。

問題文

頂点に $1$ から $N$ の番号がついた $N$ 頂点 $N$ 辺の連結な単純無向グラフ $G$ が与えられます。 $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を双方向に結んでいます。

以下の $Q$ 個のクエリに答えてください。

頂点 $x_i$ から頂点 $y_i$ に向かう単純パス（同じ頂点を $2$ 度通らないパス）が一意に定まるか判定せよ。

制約

$3 \leq N \leq 2 \times 10^5$

$1 \leq u_i < v_i\leq N$

$i \neq j$ ならば $(u_i,v_i) \neq (u_j,v_j)$

$G$ は $N$ 頂点 $N$ 辺の連結な単純無向グラフ

$1 \leq Q \leq 2 \times 10^5$

$1 \leq x_i < y_i\leq N$

入力は全て整数

解答例

閉路検出とUnionFind

$N$ 頂点 $N$ 辺の連結な無向グラフを通称「なもりグラフ」と呼びます。これは $N$ 頂点の木に1本だけ辺を追加したグラフであり、1つだけ閉路が存在します。
閉路に属する頂点の集合を $S$ とおきます。なもりグラフは、 $S$ に属する各頂点 $s_i \in S$ を根とするいくつかの部分木を、閉路で接続したグラフとみなすことができます。
以下の図は入力例2のグラフです。閉路に属する頂点は4つあるので、4つの部分木に分けられます。

木の場合、任意の2頂点 $i, j$ 間のパスは1通りに定まります。一方で、 $i, j$ の間に閉路が存在する場合、パスは1通りに定まりません。

つまりこの問題は、指定された2頂点 $i, j$ が同じ部分木に属するかどうかを判定することで解けることになります。

閉路の検出

前準備として、閉路に属する頂点 $S$ を特定します。
閉路検出は、入次数が1である頂点を順に削除していき、最後に残った頂点が閉路である、といった感じで検出することができます。^[1]

部分木の作成

次に、各部分木をUnionFind木で管理します。2頂点が同じ部分木に属する場合、パスは1通りに定まります。そうでない場合、必ず閉路を通らなければならないため、パスは2通り存在することになります^[2]。
閉路に属する各頂点 $s_i \in S$ を始点として、幅優先探索(あるいは深さ優先探索)によって部分木の全ての頂点を探索します。部分木のノードを $s_i$ と繋ぐことで、同じ部分木に属するかどうかを高速に判定できます。

実装例

以上の考察を実装したコードを以下に示します。

f.py

from typing import *
import collections

### UnionFind木の実装は省略します ###

def main():
    # 入力受け取り
    N: int = int(input())
    # グラフ
    graph: List[List[int]] = [[] for i in range(N)]
    # 入次数を記録する配列
    indegree: List[int] = [0] * N
    # グラフの構築
    for i in range(N):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        graph[u].append(v)
        graph[v].append(u)
        # 無向グラフなので入次数はどちらの頂点も増える
        indegree[u] += 1
        indegree[v] += 1

    # 閉路に属するかどうかを記録する配列
    # 入次数が1であるノード(初期状態では葉が該当)は閉路には含まれないのでFalseに設定しておく
    in_cycle: List[bool] = [len(g) != 1 for i, g in enumerate(graph)]
    # 幅優先探索によって閉路を検出する
    # 初期状態で入次数が1である頂点(すなわち葉ノード)をキューに入れておく
    candidate = collections.deque([i for i, g in enumerate(graph) if len(g) == 1])
    while candidate:
        node: int = candidate.popleft()
        for next_node in graph[node]:
            # サイクルに含まれないことが確定している場合、スキップする
            if not in_cycle[next_node]:
                continue
            # 頂点nodeを削除する(nodeが消えたことで、頂点next_nodeの入次数は1つ減る)
            indegree[next_node] -= 1
            # 頂点nodeを削除したことにより入次数が1以下になった場合、その頂点は閉路には属さない。
            if indegree[next_node] <= 1:
                in_cycle[next_node] = False
                candidate.append(next_node)

    # UnionFind木
    uf = UnionFind(N)
    # 閉路に属する頂点集合S
    cycle: Set[int] = {i for i, b in enumerate(in_cycle) if b}
    # 探索済みかどうかを表す配列(幅優先探索で使う)
    explored: List[bool] = [False] * N
    # 閉路に属する各頂点s(つまり各部分木の根)から探索を開始する
    for start in cycle:
        # 幅優先探索により、各部分木の頂点全てを根と紐付ける
        candidate = collections.deque([start])
        explored[start] = True

        while candidate:
            node: int = candidate.popleft()

            for next_node in graph[node]:
                if next_node in cycle or explored[next_node]:
                    continue
                explored[next_node] = True
                candidate.append(next_node)
                uf.unite(start, next_node)

    # クエリ処理開始
    Q: int = int(input())
    X, Y = map(list, zip(*[list(map(int, input().split())) for i in range(Q)]))
    for x, y in zip(X, Y):
        x -= 1
        y -= 1

        # 同じ部分木に属する場合、パスは1通りに定まる
        if uf.is_same(x, y):
            print("Yes")
        # そうでなければ定まらない
        else:
            print("No")


if __name__ == "__main__":
    main()

実際の提出はこちら。

脚注

けんちょんの競プロ精進記録 AOJ 2891 な◯りカット (AUPC 2018 day3 C) ↩︎
右回りと左回りがあるため。 ↩︎

GitHubで編集を提案

問題

問題文

制約

解答例

閉路検出とUnionFind

閉路の検出

部分木の作成

実装例

Discussion