Description

Submission

class Solution {
    
    int uf[100005];
    
    void ufInit() {
        for(int i = 0; i < 100005; ++i) {
            uf[i] = i;
        }
    }
    void Unite(int a, int b) {
        int aSource = Get(a);
        int bSource = Get(b);
        uf[aSource] = bSource;
    }
    
    int Get(int a) {
        if(uf[a] == a) return a;
        // cout << "Get: " << a << endl;
        return (uf[a] = Get(uf[a]));
    }
    
    int minHammingDistance(multiset<int>& s1, multiset<int>& s2) {
        
        int same = 0;
        for(auto iter1 = s1.begin(), iter2 = s2.begin(); iter1 != s1.end() && iter2 != s2.end();) {
            if(*iter1 == *iter2) {
                iter1++;
                iter2++;
                same++;
            } else if (*iter1 < *iter2) {
                iter1++;
            } else {
                iter2++;
            }
        }
        return s1.size() - same;
    }
    
    void displaySet(multiset<int>& s) {
        for(auto& e: s) {
             cout << e << " ";
        }
        cout << endl;
    }
public:
    int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
        
        ufInit();
        
        for(auto s : allowedSwaps) {
            Unite(s[0], s[1]);
        }
        
        int n = target.size();
        
        // cout << "1\n";
        // categorize by source
        unordered_map<int, multiset<int>> m1;
        unordered_map<int, multiset<int>> m2;
        
        // cout << "2.5\n";
        for(int i = 0; i < n; ++i) {
            m1[Get(i)].insert(source[i]);
            m2[Get(i)].insert(target[i]);
        }
        
        // cout << "2\n";
        // get the hamming distance for each set and aggregate
        int ret = 0;
       for(auto iter = m1.begin(); iter != m1.end(); iter++) {
           int t = iter->first;
           auto& s1 = iter->second;
           auto& s2 = m2[t];
           // print each set
           // displaySet(s1);
           // displaySet(s2);
           
           ret += minHammingDistance(s1, s2);
       }
        
        return ret;
        
    }
};