AtCoder ABC 350 G - Mediator (3D, 黄色, 600 点)

本当に色んな解法がある問題っぽい！！

• 問題へのリンク

問題概要

頂点 の 頂点からなる無向グラフがあり、最初は辺がない。以下の 2 種類のオンラインクエリに答えよ。

• クエリタイプ 1：頂点 間に辺を結ぶ
• クエリタイプ 2：頂点 の双方に隣接する頂点があるならその番号を答え、無ければ 0 と答える

なお、常にグラフが森であることが保証される。

制約

• 

解法 (1)：マージテク

最初、Union-Find において「経路圧縮」をなくせば所望の処理ができると思い込んでしまった。しかし、Union-Find では「連結成分の根同士が親子関係になる」ように辺を張るのだった。今回は、辺を張るペアが頂点 に固定されていて、これらが各連結成分の根とは限らないので上手くいかない。

しかし、実は次のように少し工夫することで上手く行く。

---

1. 適宜、頂点 を入れ替えて、「頂点 を含む連結成分のサイズ > 頂点 を含む連結成分のサイズ」となるようにする
2. 頂点 を含む連結成分について、頂点 が根となるように DFS して、頂点 を根とする根付き木にする
3. 頂点 の親を頂点 にする

---

このとき、マージテクにより、「どの頂点についても DFS によって探索されるのは高々 回である」ことが言える。

よって、全体の計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

// Union-Find
struct UnionFind {
    // core member
    vector<int> par, nex;

    // constructor
    UnionFind() { }
    UnionFind(int N) : par(N, -1), nex(N) {
        init(N);
    }
    void init(int N) {
        par.assign(N, -1);
        nex.resize(N);
        for (int i = 0; i < N; ++i) nex[i] = i;
    }
    
    // core methods
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        swap(nex[x], nex[y]);
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
    
    // get group
    vector<int> group(int x) {
        vector<int> res({x});
        while (nex[res.back()] != x) res.push_back(nex[res.back()]);
        return res;
    }
    vector<vector<int>> groups() {
        vector<vector<int>> member(par.size());
        for (int v = 0; v < (int)par.size(); ++v) {
            member[root(v)].push_back(v);
        }
        vector<vector<int>> res;
        for (int v = 0; v < (int)par.size(); ++v) {
            if (!member[v].empty()) res.push_back(member[v]);
        }
        return res;
    }
    
    // debug
    friend ostream& operator << (ostream &s, UnionFind uf) {
        const vector<vector<int>> &gs = uf.groups();
        for (const vector<int> &g : gs) {
            s << "group: ";
            for (int v : g) s << v << " ";
            s << endl;
        }
        return s;
    }
};


const int MOD = 998244353;

int main() {
    int N, Q;
    cin >> N >> Q;
    
    vector<vector<int>> G(N);
    vector<int> par(N, -1);
    UnionFind uf(N);
    
    auto dfs = [&](auto dfs, int v, int p = -1) -> void {
        if (p != -1) par[v] = p;
        for (auto ch : G[v]) {
            if (ch == p) continue;
            dfs(dfs, ch, v);
        }
    };
    
    long long res = 0;
    while (Q--) {
        long long a, b, c;
        cin >> a >> b >> c;
        
        long long A = (a * (res + 1) % MOD) % 2;
        long long u = (b * (res + 1) % MOD) % N;
        long long v = (c * (res + 1) % MOD) % N;
        
        if (A == 0) {
            if (uf.size(u) < uf.size(v)) swap(u, v);
            dfs(dfs, v);
            par[v] = u;
            uf.merge(u, v);
            G[u].push_back(v);
            G[v].push_back(u);
        } else {
            if (par[u] != -1 && par[par[u]] == v) {
                res = par[u] + 1;
            } else if (par[v] != -1 && par[par[v]] == u) {
                res = par[v] + 1;
            } else if (par[u] != -1 && par[u] == par[v]) {
                res = par[u] + 1;
            } else {
                res = 0;
            }
            cout << res << endl;
        }
    }
}