> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/union-find/1202.-smallest-string-with-swaps.md).

# 1202. Smallest String With Swaps

You are given a string `s`, and an array of pairs of indices in the string `pairs` where `pairs[i] = [a, b]` indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given `pairs` **any number of times**.

Return the lexicographically smallest string that `s` can be changed to after using the swaps.

**Example 1:**

```
Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"
```

**Example 2:**

```
Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"
```

**Example 3:**

```
Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination: 
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"
```

**Constraints:**

* `1 <= s.length <= 10^5`
* `0 <= pairs.length <= 10^5`
* `0 <= pairs[i][0], pairs[i][1] < s.length`
* `s` only contains lower case English letters.

给一个字符串s和一系列pair，能根据pair指定的index无限次swap s中对应的字符，问能得到字典序最小的字符串是什么。当多个pairs元素有交集时，它们中任何元素都能通过内部swap到任意位置，每步swap相当于往预定方向前进一步，依次从小到大让每个元素走到对应的位置。因此找出所有有交集的pair集合，并对子集做排序后放回s。合并集合用UF。

参考了[这](https://link.zhihu.com/?target=https%3A//leetcode.com/problems/smallest-string-with-swaps/discuss/388257/C%252B%252B-with-picture-union-find)。

```cpp
/*
 * @lc app=leetcode id=1202 lang=cpp
 *
 * [1202] Smallest String With Swaps
 */

// @lc code=start
class Solution {
public:
    class UF {
    public:
        vector<int> parents;
        void un(int x, int y) {
            x = find(x);
            y = find(y);
            if (x != y) {
                parents[x] = y;
            }
        }
        int find(int x) {
            while (x != parents[x]) {
                x = parents[x];
                parents[x] = parents[parents[x]];
            }
            return x;
        }
        UF(int N): parents(N) {
            for (int i = 0; i < N; ++i) {
                parents[i] = i;
            }
        }
    };
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        const int N = s.size();
        UF uf(N);
        for (const auto &p : pairs) uf.un(p[0], p[1]);
        unordered_map<int, vector<int>> m;
        for (int i = 0; i < N; ++i) m[uf.find(i)].push_back(i);
        for (const auto &p : m) {
            stringstream ss;
            for (const auto i : p.second) ss << s[i];
            auto ss_s = ss.str();
            sort(ss_s.begin(), ss_s.end());
            for (int i = 0; i < ss_s.size(); ++i) s[p.second[i]] = ss_s[i];
        }
        return s;
    }
};
// @lc code=end


```