LeetCode 1202. 交换字符串中的元素（并查集）

示例 1:
输入：s = "dcab", pairs = [[0,3],[1,2]]
输出："bacd"
解释： 
交换 s[0] 和 s[3], s = "bcad"
交换 s[1] 和 s[2], s = "bacd"

示例 2：
输入：s = "dcab", pairs = [[0,3],[1,2],[0,2]]
输出："abcd"
解释：
交换 s[0] 和 s[3], s = "bcad"
交换 s[0] 和 s[2], s = "acbd"
交换 s[1] 和 s[2], s = "abcd"

示例 3：
输入：s = "cba", pairs = [[0,1],[1,2]]
输出："abc"
解释：
交换 s[0] 和 s[1], s = "bca"
交换 s[1] 和 s[2], s = "bac"
交换 s[0] 和 s[1], s = "abc"
 
提示：
1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s 中只含有小写英文字母

class dsu
{
public:
	vector<int> f;
	dsu(int n)
	{
		f.resize(n);
		for(int i = 0; i < n; ++i)
			f[i] = i;
	}
	int find(int x)
	{
		if(x == f[x])
			return x;
		return f[x] = find(f[x]);
	}
	void merge(int x, int y)
	{
		int fx = find(x), fy = find(y);
        f[fx] = fy;
	}
};
class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
    	int n = s.size(), i, fatherid;
    	dsu uni(n);
    	for(i = 0; i < pairs.size(); ++i)
            uni.merge(pairs[i][0],pairs[i][1]);
    	unordered_map<int,multiset<char>> m;
    	for(i = 0; i < n; ++i)
    	{
            // fatherid = uni.f[i];//错误解，使用之前必须先压缩一次
    		fatherid = uni.find(i);
    		m[fatherid].insert(s[i]);
    	}
    	for(i = 0; i < n; ++i)
    	{
    		// fatherid = uni.f[i];//这样也行，上面已经压缩
            fatherid = uni.find(i);
    		s[i] = *m[fatherid].begin();
    		m[fatherid].erase(m[fatherid].begin());
    	}
    	return s;
    }
};