Propagating Edges [SoundHound Programming Contest 2018 Masters Tournament 本戦 D]

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

前提知識

• UnionFind
• マージテク

考察過程

1. 一番問題になりそうなcompleteクエリについて考えてみる
2. 本当に完全グラフになるように辺情報を持っておくのは無理そう
3. 完全グラフになっている頂点をグループ化してまとめる方針が考えられる
4. 連結になっている頂点もまとめておかないとcompleteクエリができない
5. UnionFind2つで行けそう
6. 連結になっている頂点をまとめるにはマージテクでいける
7. これだけの要素でいけそう

解法

https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/submissions/2913366

2つのUnionFindを用意する。
connectは頂点の連結関係を保持するUnionFind
completeは頂点の完全グラフ関係を保持するUnionFind
別途、辺情報を管理するsetのEも用意する。
　
checkクエリから考える。
uとvを直接結ぶ辺がある場合は「Eを確認して直接結ぶ辺がある」または「completeで同じ完全グラフにある」場合である。
　
addクエリを考えていこう。
Eに普通に辺情報を追加する。
次に、connectで連結関係を更新する。
もともと非連結であった場合は連結して、連結成分の頂点をまとめよう。
連結成分の頂点を管理するのに、gr配列を使う。
gr[i] := i番目の連結成分に含まれる頂点
gr[u]とgr[v]をまとめる場合はマージテクを使おう。
　
最後に、completeクエリを考えていこう。
対応するgrに含まれる頂点をcompleteで完全グラフ成分としてまとめる。
この時にgrには代表頂点だけ残す。
他をちゃんと消しておかないと、completeクエリばかりになった時に完全グラフを無駄に作り直してしまう。

int N, Q;
vector<int> gr[101010];
set<int> E[101010];
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
void _main() {
    cin >> N >> Q;
 
    UnionFind connect(N);
    UnionFind complete(N);
    rep(i, 0, N) gr[i].push_back(i);
 
    rep(_, 0, Q) {
        int type, u, v; cin >> type >> u >> v;
        u--; v--;
 
        if (type == 1) {
            E[u].insert(v);
            E[v].insert(u);
 
            if (complete[u] == complete[v]) continue;
            if (connect[u] == connect[v]) continue;
 
            int uu = connect[u];
            int vv = connect[v];
 
            if (gr[uu].size() > gr[vv].size()) swap(gr[uu], gr[vv]);
            fore(i, gr[uu]) gr[vv].push_back(i);
 
            connect(uu, vv);
        }
        else if (type == 2) {
            int uu = connect[u];
 
            int n = gr[uu].size();
            rep(i, 1, n) complete(gr[uu][0], gr[uu][i]);
 
            int top = gr[uu][0];
            gr[uu].clear();
            gr[uu].push_back(top);
        }
        else {
            string ans = no;
            if (complete[u] == complete[v]) ans = yes;
            if (E[u].count(v)) ans = yes;
            printf("%s\n", ans.c_str());
        }
    }
}