SoundHound Programming Contest 2018 Masters Tournament 本戦: D - Propagating Edges

問題記録 AtCoder SoundHound2018Masters本戦

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_d

問題概要

N頂点0辺の無向グラフに対してQ個のクエリが飛んでくるので順次処理せよ。

  • addクエリ: 頂点u, v間に辺を張る
  • completeクエリ: 「頂点u」と「頂点uと連結な頂点」の集合に含まれるすべての頂点間に辺を張る
  • checkクエリ: 頂点u, v間に辺が張られているかどうかを答える

N <= 105

Q <= 2*105

解法

2頂点間に辺が張られるのは当然ながらaddクエリかcompleteクエリのどちらかの影響である。このうちaddクエリの結果張られた辺は全部覚えておくことができる。一方でcompleteクエリは愚直にやると時間も空間もO(N2)かかってしまうのでここをなんとかする必要がある。結論からいうとcompleteクエリは頂点の縮約操作と見なすことで効率的に処理することができる。具体的にはaddクエリによって追加された辺に基づいて普通にグラフを構築しておき、completeクエリが来たら頂点uと連結な頂点をDFSで列挙してひとつの頂点にまとめてしまう。まとめる操作はUnionFindで実現できる。こうしておくと頂点u, v間に辺が張られているのは 「addクエリの記録にu, vがある」もしくは「uとvがUnionFindで同じ集合にまとめられている」ときのみであるから、checkクエリの際にはこれだけチェックすればよい。以降のaddクエリ、completeクエリは縮約後の頂点に読み替えて操作を行えばよい（ただし「addクエリの直接的な記録」は元の頂点で持っておく）。縮約操作は1つの頂点につきたかだか1回しか行われないので、計算量は増えない。

感想

すいません本番で通したんですが完全に嘘解法でした　自分で一瞬で撃墜してしまった

改めてちゃんとした解法を見てやったらUnionFindで管理してるのが連結頂点の集合ではなくcompleteになった集合というところで頭がこんがらがって大変だった

コード

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 Q = s[1];
    
    auto uf = new UnionFind(N);
    auto added = new bool[int][](N);
    auto G = new bool[int][](N);
    bool[int] used;

    void dfs(int n) {
        if (n in used) return;
        used[n] = true;
        foreach (m; G[n].keys) {
            if (m in used) continue;
            dfs(m);
        }
    }

    while (Q--) {
        auto q = readln.split.map!(to!int);
        int type = q[0];
        int u = q[1] - 1;
        int v = q[2] - 1;
        int up = uf.find(u);
        int vp = v >= 0 ? uf.find(v) : 0;
        if (type == 1) {
            added[u][v] = true;
            added[v][u] = true;
            G[up][vp] = true;
            G[vp][up] = true;
        } else if (type == 2) {
            auto hoge = used.keys.dup;
            foreach (h; hoge) used.remove(h);
            dfs(up);
            foreach (k; used.keys) {
                uf.unite(up, k);
                hoge = G[k].keys.dup;
                foreach (h; hoge) G[k].remove(h);
            }
        } else {
            if (v in added[u] || up == vp) {
                writeln("Yes");
            } else {
                writeln("No");
            }
        }
    }
}

class UnionFind {
    int N;
    int[] table;

    this(int n) {
        N = n;
        table = new int[](N);
        fill(table, -1);
    }

    int find(int x) {
        return table[x] < 0 ? 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);
        table[x] += table[y];
        table[y] = x;
    }
}