Description

Submission

class Solution {
    int uf[100005];

    void init() {
        for(int i = 0; i < 100005; ++i) {
            uf[i] = i;
        }
    }

    int Find(int a) {
        if(uf[a] == a) return a;
        return (uf[a] = Find(uf[a]));
    }

    void Union(int a, int b) {
        int a_ = Find(a);
        int b_ = Find(b);
        uf[a_] = b_;
    }
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        init();

        for(auto& p : pairs) {
            Union(p[0], p[1]);
        }

        // for(auto x: uf) {
        //     cout << x << " ";
        // }

        map<int, multiset<char>> str;
        map<int, multiset<int>> index;

        for(int i = 0; i < s.size(); ++i) {
            int root = Find(i);
            str[root].insert(s[i]);
            index[root].insert(i);
        }

        string ret(s.size(), ' ');

        for(auto iter = index.begin(); iter != index.end(); ++iter) {
            int root = iter->first;
            auto& set1 = iter->second;
            auto& set2 = str[root];
            auto it1 = set1.begin();
            auto it2 = set2.begin();
            for(; it1 != set1.end() && it2 != set2.end(); ++it1, ++it2) {
                ret[*it1] = *it2;
            }
        }

        return ret;
    }
};