LC1202.交换字符串中的元素

思路：并查集 + 优先队列

允许进行交换的一部分位置，可以将其视作一个集合。集合内部自由排序，排序到字典序最小即可。
确定“允许自由交换的一部分位置”，通过并查集来完成。特定集合的共同特征在于，其共享一个“代表”，即相同的find(s[i]。
建立“当前位置的集合代表”find(s[i])和对应“优先队列”priority_queue的一一映射。优先队列当中存储了当前集合的所有元素。

遍历数组，对于当前位置而言s[i]，越靠前的位置越希望有字典序小的元素，因此，将find(s[i])对应的优先队列的最小元素赋给当前位置，同时弹出最小元素。如果元素不在可交换队列当中，那么它的优先队列只有一个元素，就是原来的元素。

代码：

```cpp class UF { private:

  vector<int> fa, r;

public:

  UF(int n): fa(n), r(n, 1) {
      iota(fa.begin(), fa.end(), 0);
  }
  int find(int x) {
      if (fa[x] != x) {
          fa[x] = find(fa[x]);
      }
      return fa[x];
  }
  void merge(int x, int y) {
      x = find(x), y = find(y);
      if (x != y) {
          if (r[x] <= r[y]) {
              fa[x] = fa[y];
          } else {
              fa[y] = fa[x];
          }
          if (r[x] == r[y]) {
              r[y] += 1;
          }
      }
  }
  bool is_connected(int x, int y) {
      return find(x) == find(y);
  }

};

class Solution { public: string smallestStringWithSwaps(string s, vector>& pairs) { int n = s.size(); UF uf(n); for (int i = 0, np = pairs.size(); i < np; i++) { uf.merge(pairs[i][0], pairs[i][1]); }

    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> mp;
    for (int i = 0; i < n; i++) {
        // priority_queue<int, vector<int>, greater<int>> q;
        // mp[uf.find(i)] = q;
        mp[uf.find(i)].push(s[i] - 'a');
        // cout << uf.find(i) << " " ;
    }
    for (int i = 0; i < n; i++) {
        s[i] = mp[uf.find(i)].top() + 'a';
        mp[uf.find(i)].pop();
    }
    return s;
}

}; ```