//

// Solution1202.cpp

// Algorithm

//

// Created by Pancf on 2020/8/4.

// Copyright © 2020 Pancf. All rights reserved.

//

#include "Solution1202.hpp"

class UF

{

private:

vector<int> sz;

vector<int> cnts;

public:

UF(int length)

{

sz = vector<int>();

cnts = vector<int>(length, 1);

for (int i = 0; i < length; ++i) {

sz.push_back(i);

}

}

bool isConnected(int lhs, int rhs)

{

return find(lhs) == find(rhs);

}

int find(int i)

{

while (sz[i] != i) {

i = sz[i];

}

return i;

}

void Union(int lhs, int rhs)

{

if (isConnected(lhs, rhs)) {

return;

}

int lhs_parent = find(lhs);

int rhs_parent = find(rhs);

if (cnts[lhs_parent] < cnts[rhs_parent]) {

sz[lhs_parent] = rhs_parent;

cnts[rhs_parent] += cnts[lhs_parent];

} else {

sz[rhs_parent] = lhs_parent;

cnts[lhs_parent] += cnts[rhs_parent];

}

}

};

string Solution1202::smallestStringWithSwaps(string s, vector<vector<int>>& pairs)

{

if (s.length() == 1) {

return s;

}

// 构造连通图

UF uf((int)s.length());

for (auto pair : pairs) {

uf.Union(pair[0], pair[1]);

}

// 将每个连通图的结点构成一个集合

vector<vector<int>> m(s.length());

for (int i = 0; i < s.length(); ++i) {

m[uf.find(i)].push_back(i);

}

for (auto &ids : m) {

string ss = "";

for (auto id : ids) {

ss += s[id];

}

// 连通区域排序

sort(begin(ss), end(ss));

// 排序后放回原位

for (auto i = 0; i < ids.size(); ++i)

s[ids[i]] = ss[i];

}

return s;

}