启发式合并解法

对任意时刻、任意连通块 C，mp[C][i] 等于询问 i 的两个端点在 C中的数量（0/1/2），且只对尚未确定答案的询问保存。时间复杂度$O((n+m)α(n)+qlognlogq)$

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int f[N];
map<int,int>mp[N];
int ans[N];
void init(int n) {
    for (int i = 1 ; i <= n ; i ++) {
        f[i] = i;
    }
}

int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}

bool merge(int x , int y , int t) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) return false;
    if (mp[fx].size() < mp[fy].size()) {
        swap(fx , fy);
    }
    for (auto [x , y] : mp[fy]) {
        mp[fx][x] += y;
        if (mp[fx][x] == 2) {
            ans[x] = t;
            mp[fx].erase(x);
        }
    }
    f[fy] = fx;
    return true;
}
int main() {
    ios::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    int n , m , q;
    cin >> n >> m >> q;
    vector<pair<int,int>>e;
    init(n);
    for (int i = 1 ; i <= q ; i ++) {
        ans[i] = -1;
    }
    for (int i = 0 ; i < m ; i ++) {
        int u , v;
        cin >> u >> v;
        e.push_back(make_pair(u, v));
    }
    for (int i = 1 ; i <= q ; i ++) {
        int x , y;
        cin >> x >> y;
        if (x == y) {
            ans[i] = 0;
        }
        else {
            mp[x][i] = 1;
            mp[y][i] = 1;
        }
    }
    for (int i = 1 ; i <= m ; i ++) {
        merge(e[i - 1].first , e[i - 1].second , i);
    }
    for (int i = 1 ; i <= q ; i ++) {
        cout << ans[i] << "\n";
    }
}