https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf union find set

union find set .cpp

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> father;

void init() {
    for (int i = 0; i < father.size(); i++) {
        father[i] = i;
    }
}

int root(int x) {
    while (x != father[x]) {
        father[x] = father[father[x]];
        x = father[x];
    }
    return x;
}

void Union(int x, int y) {
    int a = root(x);
    int b = root(y);
    father[a] = b;
}

bool find(int x, int y) {
    return root(x) == root(y);
}



int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    string s;
    int n;
    cin >> s >> n;
    father.resize(s.size());
    init();
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        Union(l - 1, r - 1);
    }
    unordered_map<int, vector<int>> m;
    for (int i = 0; i < father.size(); i++) {
        m[root(i)].push_back(i);
    }
    for (const auto &p : m) {
        for (int i = 0; i < p.second.size() - 1; i++) {
            int max_idx = p.second[i];
            for (int j = 1; j < p.second.size(); j++) {
                int index = p.second[j];
                if (s[index] > s[max_idx]) {
                    max_idx = p.second[j];
                }
            }
            swap(s[max_idx], s[p.second[i]]);
        }
    }
    
    cout << s << endl;
    return 0;
}