每日一题：交换字符串中的元素

题意

给你一个字符串 $s$，以及该字符串中的一些「索引对」数组 $pairs$，其中 $pairs[i] = [a, b]$ 表示字符串中的两个索引（编号从 $0$ 开始）。

你可以 任意多次交换 在 $pairs$ 中任意一对索引处的字符。

返回在经过若干次交换后，$s$ 可以变成的按字典序最小的字符串。

Solution

假设 $i$ 可以和 $j$ 交换，$j$ 可以和 $k$ 交换，那么 $i$ 就可以和 $k$ 交换，因此是具有传递关系的。因此将互相具有传递关系的索引看作一个集合，用并查集维护。然后对于每个集合，将字母从小到大排序放置即可。时间复杂度 $O(nlog(n))$。

Code

class Solution {
public:
    int fa[100005], v[100005];
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        for (int i = 0; i < n; i++) fa[i] = i;
        for (auto& p : pairs) {
            int fx = find(p[0]), fy = find(p[1]);
            if (fx != fy) fa[fx] = fy;
            v[p[0]] = v[p[1]] = true;
        }
        int cnt = 0;
        map<int, int> mp;
        vector<int> id[100005];
        vector<char> ch[100005];
        for (int i = 0; i < n; i++) {
            if (!v[i]) continue;
            int fx = find(i);
            if (!mp[fx]) mp[fx] = ++cnt;
            id[mp[fx]].push_back(i);
            ch[mp[fx]].push_back(s[i]);
        }
        for (int i = 1; i <= cnt; i++) {
            sort(ch[i].begin(), ch[i].end());
            cout << ch[i].size() << endl;
            for (int j = 0; j < (int)id[i].size(); j++) 
                s[id[i][j]] = ch[i][j];
        }
        return s;
    }
};