给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。
你可以 任意多次交换 在 pairs 中任意一对索引处的字符。
返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。
示例 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 中只含有小写英文字母
我们由示例1分析得知，[0,3]，[1,2]这两个集合里对应元素可以存在于集合里任意位置，比如[d,b]在[0,3]里可以是[d,b]也可以是[b,d]. 我们再举一个例子：s = “dcab”，集合为[0,3], [1,2]，[0,2]. [0,1,3,2]是一个连通图，因此元素可以通过各种交换走到任一位置，从而实现最小字典序。 因此我们可以将pairs[x,y]看成x顶点和y顶点存在一条无向边，我们的任务就是将该图的各个连通分量按照字典序排列，最后的结果就是能实现的最小字典序。 采用并查集算法，将各个顶点并成一个个集合树，一棵集合树表示一个连通分量。我们再用一个二维数组将集合存起来，取出集合中的顶点所对应的字母并将其进行排序，再将排序后的字母放回顶点。 下面上代码。
#include <bits/stdc++.h> #define MAX 100010 using namespace std; class Solution { public: int pre[MAX]; int h[MAX]; void init() //初始化 { for(int i = 0;i < MAX;i++) pre[i] = i, h[i] = 1; } int Find(int x) //查找根节点 { if(x == pre[x]) return x; return pre[x] = Find(pre[x]); } void Union(int x, int y) //两个集合并起来 { int rx = Find(x); int ry = Find(y); if(rx == ry) return; if(h[rx] > h[ry]) pre[ry] = rx; else if(h[rx] < h[ry]) pre[rx] = ry; else pre[ry] = rx, h[rx]++; } string smallestStringWithSwaps(string s, vector<vector<int> >& pairs) { init(); //初始化 for(int i = 0;i < pairs.size();i++) //将pairs两个数所在集合并起来 Union(pairs[i][0], pairs[i][1]); vector<vector<int> > setv(s.length()); //创建一个用来存集合的二维数组，行数为字符串长度 for(int i = 0;i < s.length();i++) setv[Find(i)].push_back(i); //创建集合，节点存进根节点所在行 for(int i = 0;i < s.length();i++) { priority_queue<char,vector<int>,greater<int> > q; //从小到大排序的优先队列 if(pre[i] == i) //判断i为根节点 { for(int j = 0;j < setv[i].size();j++) //将集合里元素对应的字母存进优先队列排序 q.push(s[setv[i][j]]); for(int j = 0;j < setv[i].size();j++) //将排序好的字母按集合元素一一对应 { int index = setv[i][j]; s[index] = q.top(); q.pop(); } } } return s; } };