分析
参考上周日的周赛第三题: https://www.acwing.com/activity/content/code/content/680613/
设一个并查集,利用pairs数组将连通块建立起来。
之后将同一连通块的字母加入到faset数组中,并对其排序。
最后将每一个位置的字母变成最小序即可。
C++ 代码
class Solution {
public:
int fa[100010];
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
string faset[100010];
int cnt[100010];
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) fa[find(p[0])]=find(p[1]); //建立连通块
// for(int i=0;i<n;i++) cout<<fa[i]<<" ";
for(int i=0;i<n;i++)
{
faset[find(i)]+=s[i]; //将字母加入到对应的faset[]中
}
for(int i=0;i<n;i++) sort(faset[i].begin(),faset[i].end());
for(int i=0;i<n;i++)
{
s[i]=faset[find(i)][cnt[find(i)]++]; //找到该位字母所在的faset集合,取该集合最前面的元素替换
}
return s;
}
};