https://atcoder.jp/contests/arc045/tasks/arc045_d

問題概要

整数Nと、XY平面上の(2N+1)個の点が与えられる。各点はX座標またはY座標が同じ他の1点とペアになることができる。ただしすでにペアをつくっている点が他の点とペアになることはできない。すべての点について「その点だけを除いたとき残された点でN個のペアを作ることができるか」を判定せよ。

N <= 10⁵

解法

まずペアになることが可能な点同士で辺を張ってグラフをつくる。ここで異なる連結成分に属する点同士はペアにできないので、各連結成分は独立に考えてよい。

このグラフの重要な性質として「連結成分の頂点数が偶数であるならば、その連結成分内ではすべての点をペアにすることが可能」というものがある（詳しくは公式解説参照）。よって問題は以下のように言い換えることが可能である。

グラフからある点を除いたとき、すべての連結成分の頂点数が偶数となるか？

自明なパターンから処理していくと、まず頂点数が奇数であるような連結成分が2個以上ある場合、題意を満たすようなペア作りは不可能である（どの点を除いたとしても必ずひとつは奇数の連結成分が残ってしまうため）。

そうでない場合、つまり頂点数が奇数であるような連結成分がただひとつである場合、まず除く点の属する連結成分の頂点数が偶数のときはNGになる（上と同じ理由）。

残るパターンは頂点数が奇数であるような連結成分がただひとつで、かつ除く点の属する連結成分の頂点数が奇数の場合である。このとき、まず除く点が関節点でなければ無条件でOKとなる。なぜならその点を除いても連結成分はバラバラにならないので、結果として残る連結成分はすべて偶数となるからである。逆に関節点の場合、その点を取り除くと連結成分が分裂する。なので分かれた先の各連結成分が偶数であるかを確認する必要がある。この問題でつくったグラフの場合、関節点を取り除いた結果として連結成分が3個以上に分かれることはない（必ず2つになる）ので、関節点検出のときにつくるDFS木上で部分木の個数をかぞえるようなことをすれば分裂後の頂点数の偶奇はわかる（具体的にはある関節点uを取り除いたとき、その連結成分は「DFS木上において関節点uの子であってlow[v]>=ord[u]であるような頂点vを根とする部分木に含まれるすべての点の集合」と「それとu以外のすべての点の集合」の2つの連結成分に分かれる。2つなのでどちらかの偶奇だけがわかればよく、DFS木上では部分木のサイズを数えるほうが簡単）。

感想

なんかややこしくてつらかった　関節点とか橋って問題によって求められる操作が微妙に違っててうまいことライブラリにするのむずない？

コード (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;

void main() {
    auto N = readln.chomp.to!int;
    auto P = (2*N+1).iota.map!(i => readln.split.map!(to!int).array).array;

    auto X = new Tuple!(int, int)[][](2*N+1);
    auto Y = new Tuple!(int, int)[][](2*N+1);
    foreach (i; 0..2*N+1) {
        X[P[i][0]-1] ~= tuple(P[i][1]-1, i);
        Y[P[i][1]-1] ~= tuple(P[i][0]-1, i);
    }

    auto G = construct_graph(N, X, Y);
    auto U = construct_uf(N, G);

    if ((2*N+1).iota.map!(i => U.table[i] < 0 && -U.table[i] % 2 == 1).sum != 1) {
        foreach (i; 0..2*N+1) writeln("NG");
        return;
    }

    G.articulation_points;

    debug {
        G.adj.each!writeln;
        G.is_articulation.writeln;
        G.dfs_subtree.writeln;
    }

    foreach (i; 0..2*N+1) {
        if (-U.table[U.find(i)] % 2 == 0) {
            writeln("NG");
        } else if (!G.is_articulation[i]) {
            writeln("OK");
        } else {
            writeln(G.divide_evenly[i] ? "OK" : "NG");
        }
    }
}

class UndirectedGraph {
    int N;
    int[][] adj;
    int[] dfs_subtree;
    bool[] is_articulation;
    bool[] divide_evenly;

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

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

    void articulation_points() {
        auto ord = new int[](N);
        auto low = new int[](N);
        auto dfs_tree = new int[][](N);
        auto used = new bool[](N);
        dfs_subtree = new int[](N);
        is_articulation = new bool[](N);
        divide_evenly = new bool[](N);
        int cnt;

        int dfs(int n, int p) {
            ord[n] = cnt++;
            low[n] = ord[n];
            used[n] = true;
            foreach (m; adj[n]) {
                if (m == p) continue;
                if (used[m]) low[n] = min(low[n], ord[m]);
                else low[n] = min(low[n], dfs(m, n)), dfs_tree[n] ~= m; 
            }
            return low[n];
        }

        int dfs2(int n, int p) {
            dfs_subtree[n] = 1;
            foreach (m; dfs_tree[n]) {
                if (m == p) continue;
                auto s = dfs2(m, n);
                dfs_subtree[n] += s;
            }
            return dfs_subtree[n];
        }

        foreach (i; 0..N) {
            cnt = 0;
            if (!used[i]) {
                dfs(i, -1);
            }
        }

        foreach (i; 0..N) {
            if (ord[i] == 0 && dfs_tree[i].length >= 2) {
                is_articulation[i] = true;
            } else if (ord[i] != 0 && dfs_tree[i].map!(j => (low[j] >= ord[i])).any) {
                is_articulation[i] = true;
            }
        }

        foreach (i; 0..N) {
            if (ord[i] == 0) {
                dfs2(i, -1);
            }
        }

        foreach (i; 0..N) {
            if (!is_articulation[i]) continue;
            if (ord[i] == 0) {
                divide_evenly[i] = dfs_subtree[dfs_tree[i][0]] % 2 == 0;
            } else {
                divide_evenly[i] = dfs_tree[i].filter!(j => low[j] >= ord[i]).map!(j => dfs_subtree[j]).sum % 2 == 0;
            }
        }
    }
}

class UnionFind {
    int N;
    int[] table;
    int[][] group;

    this(int n) {
        N = n;
        table = new int[](N);
        fill(table, -1);
        group = N.iota.map!(i => [i]).array;
    }

    int find(int x) {
        return table[x] < 0 ? x : (table[x] = find(table[x]));
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (table[x] > table[y]) swap(x, y);
        group[x] ~= group[y];
        group[y] = [];
        table[x] += table[y];
        table[y] = x;
    }
}


UndirectedGraph construct_graph(int N, Tuple!(int, int)[][] X, Tuple!(int, int)[][] Y) {
    auto G = new UndirectedGraph(2*N+1);
    foreach (i; 0..2*N+1) {
        X[i].sort();
        foreach (j; 0..X[i].length.to!int-1) {
            G.add_edge(X[i][j][1], X[i][j+1][1]);
            if (j + 2 < X[i].length) {
                G.add_edge(X[i][j][1], X[i][j+2][1]);
            }
        }
    }
    foreach (i; 0..2*N+1) {
        Y[i].sort();
        foreach (j; 0..Y[i].length.to!int-1) {
            G.add_edge(Y[i][j][1], Y[i][j+1][1]);
            if (j + 2 < Y[i].length) {
                G.add_edge(Y[i][j][1], Y[i][j+2][1]);
            }
        }
    }
    foreach (i; 0..2*N+1) {
        G.adj[i] = G.adj[i].dup.sort().uniq.array;
    }
    return G;
}

UnionFind construct_uf(int N, UndirectedGraph G) {
    auto uf = new UnionFind(2*N+1);
    foreach (i; 0..2*N+1) foreach (j; G.adj[i]) uf.unite(i, j);
    return uf;
}

nebukuro09の日記

AtCoder Regular Contest 045: D - みんな仲良し高橋君

問題概要

解法

感想

コード (D言語)