AtCoder Regular Contest 039: D - 旅行会社高橋君

https://atcoder.jp/contests/arc039/tasks/arc039_d

問題概要

N頂点M辺の無向グラフとQ個の旅行計画が与えられる。各旅行計画は始点、中継点、終点をあらわす頂点の組(A, B, C)からなる。各旅行計画について、一度も同じ辺を通ることなく始点→中継点→終点と移動することが可能かどうかを求めよ。同じ頂点は何度通っても良い。

N <= 105

M <= 2 * 105

Q <= 105

解法

グラフを二重辺連結成分分解し各成分をひとつの頂点と見なすと、これは各成分が元のグラフにおける橋によって繋がれた木になる(この辺の話は「二重辺連結成分分解」でググった方が早い)。

この木上で問題を考えると、木の各辺が必ず橋になっていることから、結局「始点Aが属する頂点 -> 中継点Bが属する頂点 -> 終点Cが属する頂点」の最短距離での移動が単純パスになっているか、という問題と同義である。この判定のためにLCAを使うことができる。自分は以下のような場合分けでやった。

  1. AがCの祖先であるとき <=> LCA(A, C) = A のとき このとき条件が成り立つのは「BがAとCの間にある」、つまり「AがBの祖先であり、BがCの祖先である」ときのみである。すなわち LCA(A, B) = A かつ LCA(B, C) = B が成り立っていればよい。
  2. CがAの祖先であるとき <=> LCA(A, C) = C のとき 1の逆をやればよい。
  3. 上記1, 2のどちらにも当てはまらないとき このときBはAかCどちらかの祖先でなくてはならず、またそうでない方とBのLCAはAとCのLCAと等しい。

まとめるとこの問題は 1. 二重辺連結成分分解をする 2. 分解後の各成分で木をつくる 3. 木に対してLCAとかをやってA->B->Cを通る単純パスが作れるかを判定する という3ステップで解くことが可能である。二重辺連結成分分解(とそれによる木の構築)の実装については例えば以下の Spaghetti Source のコードが参考になった。

(補足の追記)上の話だとA, B, Cが同じ連結成分に属している場合には必ず旅行可能である(つまり同じ二重辺連結成分内の任意の3点a, b, cに対して、a->b->cと移動するような単純パスが必ず存在する)と暗に仮定しているが、このことについての証明は公式解説に詳しい。(自分が解いたときはたぶんできるだろと思って決め打ちでやってしまったが、よく考えてみると全然自明な感じではなかった)

感想

二重辺連結成分分解のライブラリとLCAのライブラリをたまたま別件で作っていて、この問題で組み合わせて使ってみたらかなり便利だった コードの再利用ってすごいですね 対談形式のプログラミング入門の本に出てくる人みたいな感想ですいません

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];

    auto G = new UndirectedGraph(N);
    foreach (i; 0..M) {
        s = readln.split.map!(to!int);
        G.add_edge(s[0]-1, s[1]-1);
    }

    auto T = new BridgeBlockTree(G);
    auto L = new LCA(T.block.length.to!int, 0);

    foreach (i; 0..T.block.length.to!int) {
        foreach (j; T.adj[i]) {
            if (i < j) {
                L.add_edge(i, j);
            }
        }
    }

    bool check() {
        s = readln.split.map!(to!int);
        auto a = T.index[s[0] - 1];
        auto b = T.index[s[1] - 1];
        auto c = T.index[s[2] - 1];
        auto ab = L.lca(a, b);
        auto bc = L.lca(b, c);
        auto ca = L.lca(c, a);

        if (ca == a) {
            return ab == a && bc == b;
        } else if (ca == c) {
            return bc == c && ab == b;
        } else {
            return (ab == ca && bc == b) || (bc == ca && ab == b);
        }
    }


    auto Q = readln.chomp.to!int;

    while (Q--) {
        writeln( check ? "OK" : "NG" );
    }
}



class UndirectedGraph {
    int N;
    int[][] adj;

    this (int N) {
        this.N = N;
        adj = new int[][](N);
    }

    void add_edge(int u, int v) {
        adj[u] ~= v;
        adj[v] ~= u;
    }
}

class BridgeBlockTree : UndirectedGraph { // 二重辺連結成分分解 (橋で分解したあとの木)
    int[] index;
    int[][] block;
    Tuple!(int, int)[] bridges;

    this (UndirectedGraph g) {
        int n = 0;
        int cnt = 0;

        bridges = detect_bridges(g);
        auto is_bridge = new bool[int][](g.N);
        foreach (b; bridges) {
            is_bridge[b[0]][b[1]] = true;
            is_bridge[b[1]][b[0]] = true;
        }

        index = new int[](g.N);
        auto used = new bool[](g.N);

        void dfs(int n) {
            index[n] = block.length.to!int - 1;
            block.back ~= n;
            used[n] = true;
            foreach (m; g.adj[n]) {
                if (used[m] || m in is_bridge[n]) continue;
                dfs(m);
            }
        }

        foreach (u; 0..g.N) {
            if (used[u]) continue;
            block.length += 1;
            dfs(u);
        }

        super(block.length.to!int);

        foreach (u; 0..g.N) {
            foreach (v; g.adj[u]) {
                if (u < v && index[u] != index[v]) {
                    adj[index[u]] ~= index[v];
                    adj[index[v]] ~= index[u];
                }
            }
        }
    }

    Tuple!(int, int)[] detect_bridges(UndirectedGraph g) {
        Tuple!(int, int)[] bridges;
        int cnt = 0;
        auto ord = new int[](g.N);
        auto low = new int[](g.N);
        fill(ord, -1);
        fill(low, -1);

        void dfs(int n, int p) {
            ord[n] = low[n] = cnt++;
            foreach (m; g.adj[n]) {
                if (m == p) continue;
                if (ord[m] == -1) dfs(m, n);
                low[n] = min(low[n], low[m]);
                if (ord[n] < low[m]) bridges ~= tuple(n, m);
            }
        }

        dfs(0, -1);
        return bridges;
    }
}


class LCA {
    int n, root, lgn;
    int[][] g;
    int[] depth;
    int[][] dp;
    bool constructed = false;

    this(int n, int root) {
        this.n = n;
        this.root = root;
        lgn = bsr(n) + 3;
        g = new int[][](n);
        depth = new int[](n);
        dp = new int[][](n, lgn);
    }

    void add_edge(int u, int v) {
        g[u] ~= v;
        g[v] ~= u;
    }

    void construct() {
        auto stack = new Tuple!(int, int, int)[](n+10);
        int sp = 0;
        stack[0] = tuple(root, -1, 0);
        while (sp >= 0) {
            auto u = stack[sp][0];
            auto p = stack[sp][1];
            auto d = stack[sp][2];
            sp -= 1;
            dp[u][0] = p;
            depth[u] = d;
            foreach (v; g[u]) if (v != p) stack[++sp] = tuple(v, u, d+1);
        }

        foreach (k; 0..lgn-1)
            foreach (i; 0..n)
                dp[i][k+1] = (dp[i][k] == -1) ? -1 : dp[dp[i][k]][k];
        constructed = true;
    }

    void dfs(int u, int p, int d) {
        dp[u][0] = p;
        depth[u] = d;
        foreach (v; g[u]) if (v != p) dfs(v, u, d+1);
    }

    int lca(int a, int b) {
        if (!constructed) construct;
        if (depth[a] < depth[b]) swap(a, b);

        int diff = depth[a] - depth[b];
        foreach_reverse (i; 0..lgn) if (diff & (1<<i)) a = dp[a][i];

        if (a == b) return a;

        int K = lgn;
        while (dp[a][0] != dp[b][0]) {
            foreach_reverse (k; 0..lgn) {
                if (dp[a][k] != dp[b][k]) {
                    a = dp[a][k];
                    b = dp[b][k];
                    K = k;
                }
            }
        }

        return dp[a][0];
    }
}