1
class Solution {
2
 public:
3
  vector<int> parent;
4

5
  int findParent(int n) {
6
    if (parent[n] == n) return n;
7
    return parent[n] = findParent(parent[n]);
8
  }
9

10
  string smallestStringWithSwaps(string s, vector<vector<int>> &pairs) {
11
    map<int, set<int>> mp;
12
    parent.resize(s.size());
13
    string ans = s;
14

15
    for (int i = 0; i < s.length(); i++) parent[i] = i;
16

17
    for (auto pair : pairs) {
18
      int p1 = findParent(pair[0]), p2 = findParent(pair[1]);
19
      if (p1 != p2) parent[p2] = p1;
20
    }
21

22
    for (auto pair : pairs) {
23
      int p = findParent(pair[0]);
24
      mp[p].insert(pair[0]);
25
      mp[p].insert(pair[1]);
26
    }
27

28
    for (auto it : mp) {
29
      vector<char> part;
30
      set<int> idx = it.second;
31

32
      for (auto index : idx) part.push_back(s[index]);
33

34
      sort(part.begin(), part.end());
35

36
      auto index = idx.begin();
37
      for (auto x : part) ans[*index] = x, ++index;
38
    }
39

40
    return ans;
41
  }
42
};