leetcode

0 class UnionFind {

1 vector<int> root, rank;

2

3 public:

4 UnionFind(int n) : root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); }

5

6 int find(int x) {

7 if (x == root[x]) return x;

8 return root[x] = find(root[x]);

9 }

10

11 void join(int x, int y) {

12 x = find(x), y = find(y);

13

14 if (x != y) {

15 if (rank[x] > rank[y]) swap(x, y);

16 root[y] = x;

17 rank[x] += x == y;

18 }

19 }

20 };

21

22 class Solution {

23 public:

24 string smallestStringWithSwaps(string s, vector<vector<int>> &pairs) {

25 UnionFind uf(s.size());

26 vector<vector<char>> vs(s.size());

27

28 for (auto &p : pairs)

29 uf.join(p[0], p[1]);

30

31 for (int i = 0; i < s.size(); i++)

32 vs[uf.find(i)].push_back(s[i]);

33

34 for (auto &s : vs)

35 sort(s.rbegin(), s.rend());

36

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

38 int index = uf.find(i);

39 s[i] = vs[index].back();

40 vs[index].pop_back();

41 }

42 return s;

43 }

44 };