Permutation Swaps!

• Time : $O(elogv + vlogv)$
• Space : $O(v)$

#include <bits/stdc++.h>

int uf[101010];

int find(int u) {
    return uf[u] == u ? u : uf[u] = find(uf[u]);
}

void uni(int u, int v) {
    int pu = find(u), pv = find(v);
    uf[pu] = uf[pv] = min(pu,pv);
}

int Solution::solve(vector<int> &A, vector<int> &B, vector<vector<int> > &C) {
    iota(begin(uf), end(uf), 0);
    for(auto c : C) {
        int u = c[0] - 1, v = c[1] - 1;
        uni(u,v);
    }
    unordered_map<int, unordered_map<int, int>> freq;
    for(int i = 0; i < A.size(); i++) {
        int pi = find(i);
        freq[pi][A[i]] += 1;
        freq[pi][B[i]] -= 1;
        if(freq[pi][A[i]] == 0) freq[pi].erase(A[i]);
        if(freq[pi][B[i]] == 0) freq[pi].erase(B[i]);
        if(freq[pi].size() == 0) freq.erase(pi);
    }
    return freq.size() == 0;
}