【題解】AtCoder ABC 183F – Confluence

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

int n, q, c[200005], p[200005];
map <int, int> mp[200005];

int f(int x){
    if (p[x] < 0) return x;
    return p[x] = f(p[x]);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> c[i];
        p[i] = -1;
        mp[i][c[i]]++;
    }
    int t, a, b;
    while (q--){
        cin >> t >> a >> b;
        if (t == 1){
            a = f(a);
            b = f(b);
            if (a == b) continue;
            if (-a < -b) swap(a, b);
            for (auto i:mp[b]){
                mp[a][i.first] += i.second;
            }
            p[a] += p[b];
            p[b] = a;
        }
        else cout << mp[f(a)][b] << "\n";
    }
}