問題概要

初期状態では頂点数 $N$ 、辺数 0 のグラフがある。頂点番号は $1, 2, \dots, N$ である。次の $Q$ 回のクエリに答えよ。

クエリタイプ 1：頂点 $u, v$ 間に辺を張る
クエリタイプ 2：頂点 $v$ を含む連結成分に含まれる頂点の番号にうち、 $k$ 番目に大きいものを答える (存在しない場合は -1)

制約

$1 \le N, Q \le 2 \times 10^{5}$

考えたこと

クエリタイプ 1 のみを見ると、いかにも Union-Find が有効に思える。さらにクエリタイプ 2 も Union-Find で扱える。

一般に、Union-Find の各グループになんらかの情報を持たせたいとき、グループの根頂点に情報を持たせるようにするのがよい。ここでは、次の情報を持たせよう。

comp[r]：Union-Find において根頂点を $r$ とするようなグループについて、そのグループに含まれる頂点番号の上位 10 個の値 (10 個未満の場合はすべての値)

Union-Find 上で、頂点 $u$ を含むグループ $U$ と頂点 $v$ を含むグループ $V$ を併合するときのことを考えよう。ここでは $U$ を含むグループの方がサイズが小さいとする。このとき

頂点 u の親を頂点 v にする
comp[u] を comp[v] に併合して、comp[u] を clear() する

というようにすればよい。後者は上位 10 個しかもたないことに注意しよう。 $K$ をクエリタイプ 2 に登場する $k$ の最大値としたとき、comp に関する処理の計算量は $O(K \log K)$ と評価できる。

全体の計算量は、 $O(N + Q \alpha(N) K \log K)$ となる。

コード

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

struct UnionFind {
    vector<int> par;  // いつもの
    vector<vector<int>> comp;  // 値に対してのみ、連結成分に含まれる頂点を上位 10 だけ格納する

    UnionFind(int N) : par(N, -1), comp(N) {
        for (int v = 0; v < N; v++) comp[v] = {v};
    }

    int root(int v) {
        if (par[v] < 0) return v;
        else return par[v] = root(par[v]);
    }

    int size(int v) {
        return -par[root(v)];
    }

    void merge(int u, int v) {
        u = root(u), v = root(v);
        if (u == v) return;
        if (size(u) > size(v)) swap(u, v);

        // u を v にマージする
        for (auto val : comp[u]) comp[v].push_back(val);
        comp[u].clear();
        sort(comp[v].begin(), comp[v].end(), greater<int>());
        if (comp[v].size() > 10) comp[v].resize(10);

        // u の親を v にする
        par[v] += par[u];
        par[u] = v;
    }
};

int main() {
    int N, Q;
    cin >> N >> Q;
    UnionFind uf(N);
    while (Q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int u, v;
            cin >> u >> v, u--, v--;
            uf.merge(u, v);
        } else {
            int v, k;
            cin >> v >> k, v--;
            const auto &comp = uf.comp[uf.root(v)];
            if (k > comp.size()) cout << -1 << endl;
            else cout << comp[k-1]+1 << endl;
        }
    }
}