トップ > AOJ 1430 Even Division

AOJ 1430 Even Division

$$ \gdef\V{\mathcal{V}} \gdef\set#1{\lbrace #1 \rbrace} \gdef\card#1{\vert #1 \vert} \gdef\sqbrack#1{\lbrack #1 \rbrack} \gdef\induced#1#2{#1\sqbrack{#2}} $$

これは 帰ってきた AOJ-ICPC Advent Calendar 2022 - Adventar 15日目の記事です。

2021年の横浜Regionalで使われた問題のネタバレを大いに含みます。練習に使う予定がある方は注意してください。

問題

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1430

以下要約:

$N$ 頂点 $M $ 辺の連結な単純無向グラフ $G$ が与えられる。$V = \set{0, \ldots, N - 1}$ の部分集合族 $\V = \set{V _ 1, \ldots, V _ k} \subseteq 2 ^ V$ が以下の 4 つの条件を全て満たすとき、またそのときに限って「$\V$ は $G$ の even division である」という。

  1. $\V$ は $V$ の 分割 である。
  2. 任意の $V _ i \in \V$ について $\card{V _ i}$ は 正の偶数 である。
  3. 任意の $V _ i \in \V$ について、$V _ i$ による 誘導部分グラフ $\induced{G}{V _ i}$ は連結 である。
  4. $\V$ の 細分 $\V'$ であって $\V' \neq \V$ かつ上記 1,2,3 を満たすものは存在しない。

$G$ の even division を 1 つ求めよ。

制約

  • $2 \leq N \leq 10 ^ 5$
  • $N$ は偶数
  • $N - 1 \leq M \leq 10 ^ 5$
  • 与えられるグラフは連結であり、多重辺や自己ループを含まない。

解法

方針: $G$ の DFS 木 $T$ を取り、ボトムアップに成分を取り除くことを繰り返して even division を構築する。

まず、$T$ の部分木であって頂点数が偶数のものがあればその部分木は切り離してもよい (i.e. 条件1,2,3 を満たすことは保たれる) ので、切り離す。操作のイメージは図 1 を参照。以降の図においては断りなく木を構成する辺を黒で、後退辺を赤で描く。

図1. 偶数サイズの部分木の切り離し

この操作を可能な限り繰り返すことで $T$ はいくつかの DFS 木 $T _ 1, \ldots, T _ l$ に分割される。各 DFS 木 $T _ i$ は次の性質 $(\star)$ を満たす。

性質 $(\star)$
頂点数が偶数の連結グラフであり、自身を除いた全ての部分木のサイズは奇数である。

$T _ i$ 毎に独立に分割が求まればよいので、以降は $T$ が $(\star)$ を満たすと仮定する。

$T$ の後退辺 $\set{x, y}$ に注目する。後退辺は必ず先祖/子孫関係にある2頂点を結ぶので、$x$ は $y$ の先祖であるとして一般性を失わない。図2のような、$xy$ パスに沿った分割の操作を考える。

図2. 後退辺の除去

図2において青で囲った成分の1つ $C$ に注目する。$C$ において部分木のサイズが変化するのは根のみであり、奇数サイズの子部分木を取り除いているので $\card{C}$ は偶数である。$C$ 自身以外の部分木のサイズは奇数であったので、$C$ は $(\star)$ の性質を満たしている。

続いて、橙で囲った成分 $C'$ に注目する。後退辺 $\set{x, y}$ を木を構成する辺として用いることで、$C'$ は再び DFS 木となり、$(\star)$ の性質を満たす。

従って、この分割に関して次が成り立つ:

  • 後退辺が 1 つ減る。
  • 得られた全ての連結成分は $(\star)$ を満たす。

これを可能な限り繰り返すことで得られた成分たちには後退辺が存在しない。即ち、最終的には森が得られる。

各成分が $(\star)$ を満たすように分割を繰り返したので、森の各連結成分もまた $(\star)$ を満たす。ここで、以下の事実が重要である。$V(T)$ は $T$ の頂点全体の集合を表す。

重要な事実
木 $T$ が $(\star)$ を満たすならば、$\set{V(T)}$ は even division である。

証明

$V(T)$ の任意の 2 分割 $\set{A,V(T) \setminus A}$ が条件 1,2,3 のいずれかに違反することを示せば十分。$\set{A,V(T) \setminus A}$ が条件 1, 2, 3 を満たすと仮定する。

条件 2 より $A\neq \emptyset$ かつ $V(T) \setminus A\neq \emptyset$ が必要である。従って、条件 3 を満たすような分割は $T$ の辺を 1 本削除することに対応する。しかし、辺を 1 本削除することで得られる $2$ つの成分のサイズは $(\star)$ の性質より必ず奇数となり、条件 2 に違反する。$\blacksquare$

以上で even division が得られた。この手続きは全体 $O(N + M)$ 時間で可能であり、十分高速である。

実装

実装は結構大変で、私はかなりバグらせました。

以下の実装は2重DFSで書かれていて、DFS木を構築する外側のDFSにおいて偶数サイズの部分木を発見したら後退辺を除去する内側のDFSを呼んでいます。

外側はともかく内側のDFSを正確に処理するのは結構大変で、全域森を管理を上手くやる必要があります。ここでは親へのリンク $\mathrm{par}$ を用意して、常に $\set{\set{v, \mathrm{par}\sqbrack{v}} \mid \mathrm{par}\sqbrack{v} \neq -1}$ が全域森の辺集合と一致するように $\mathrm{par}$ を更新しています。$\mathrm{par}$ を使えばある辺が全域森に属するかどうかを簡単に判定できます (実装例の is_tree_edge がそれ)。

実装する上で特に気を付けるべき点は以下の3つくらいでしょうか。

  • 先祖方向の後退辺は適切に skip する。実装例では深さの配列 dep を用意してその大小で先祖方向 or 子孫方向の判定をしています。
  • 内側のDFSで後退辺が指す先が既に切り離された頂点である (i.e. 異なる成分に属している) 可能性があることに注意する。
  • $\mathrm{par}$ の更新を忘れない。

提出リンク

#include <iostream>
#include <utility>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    std::vector<int> dep(n);      // 深さ。後退辺の方向 (先祖方向 or 子孫方向) の判定に用いる
    std::vector<int> par(n, -1);  // 全域森の管理。{v, par[v]} が全域森の辺

    auto is_tree_edge = [&par](int u, int v) { return par[u] == v or par[v] == u; };

    std::vector<int8_t> visit(n);    // 既に訪問した頂点かどうか
    std::vector<int8_t> removed(n);  // 既に切り離された頂点かどうか

    std::vector<std::vector<int>> ans;
    auto collect = [&](int r) {  // 全域森で r が属する成分の頂点を集めて答えに追加
        auto &cmp = ans.emplace_back();
        auto collect_rec = [&](auto collect_rec, int cur, int prv) -> void {
            cmp.push_back(cur);
            removed[cur] = true;
            for (int nxt : g[cur]) if (is_tree_edge(cur, nxt) and nxt != prv) {
                collect_rec(collect_rec, nxt, cur);
            }
        };
        collect_rec(collect_rec, r, -1);
    };

    auto remove_even_subtrees = [&](auto remove_even_subtrees, int root) -> int {
        visit[root] = true;
        int sub_size = 1;
        for (int v : g[root]) if (not visit[v]) {
            par[v] = root;
            dep[v] = dep[root] + 1;
            sub_size += remove_even_subtrees(remove_even_subtrees, v);
        }

        if (sub_size % 2 == 0) {
            par[root] = -1; // 全域森から辺を削除 (root を根とする部分木を切り離す)
            auto remove_backward_edges = [&](auto remove_backward_edges, int u, int par_u) -> void {
                for (int v : g[u]) if (v != par_u) {
                    if (is_tree_edge(u, v)) {
                        remove_backward_edges(remove_backward_edges, v, u);
                    } else if (not removed[v] and dep[v] > dep[u]) { // 子孫方向の削除されていない後退辺
                        // 全域森から辺 {v, par[v]} を削除して辺 {v, u} を追加 / uとvの間にある頂点 r を列挙
                        for (int r = std::exchange(par[v], u); r != u;) {
                            // 辺 {r, par[r]} を削除
                            int nxt_r = std::exchange(par[r], -1);
                            collect(r);
                            r = nxt_r;
                        }
                    }
                }
            };
            remove_backward_edges(remove_backward_edges, root, -1);
            collect(root);
        }
        return sub_size;
    };
    remove_even_subtrees(remove_even_subtrees, 0);

    std::cout << ans.size() << '\n';
    for (const auto& cmp : ans) {
        std::cout << cmp.size();
        for (int v : cmp) std::cout << ' ' << v;
        std::cout << '\n';
    }
}