题解 | #多重映射#

发一下题的一个题解，其实这题在atcoder有个简单版本，就在前不久的ABC的C题，Many replacemant，简单版本的数据范围比较小，每次都可以暴力修改，但是这题的数据范围是比较大的，显然不能每次遍历所有范围进行修改。而且这题直觉上就是一个并查集，但是不能直接用并查集做，因为涉及到删边，并查集不好维护，考虑并查集加map映射，我们把这个题目分成两层进行维护，第一层就是数组内各个元素的并查集，如果他们被修改成的元素相同，则放到同一个集合里，第二层就代表这个集合被映射成的值，容易发现第一层的并查集并不会发生删边，我们只需要不断的维护这个集合以及他应该映射到的值就可以，我们使用两个来维护第二层的关系，代表这个集合应该映射到的值，代表映射为的集合（集合均使用这个集合的祖先来代表），具体细节见代码：

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define gcd __gcd
using namespace std;
int fa[1000005];
int _find(int x){
    if (x == fa[x]) return x;
    return fa[x] = _find(fa[x]);
}
void join(int x, int y){ //将x的祖先的祖先设置成y的祖先，需要注意这个合并顺序
    fa[_find(x)] = _find(y);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--){
        int n, m;
        cin >> n >> m;
        map<int, int> mp1, mp2;
        vector<int> a(n + 5);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            fa[a[i]] = a[i]; //初始化并查集，注意不能每次都对整个值域初始化，用到哪个初始化哪个
            mp1[a[i]] = a[i]; //映射初始化
            mp2[a[i]] = a[i];
        }
        while (m--){
            int x, y;
            cin >> x >> y; //将所有x都修改成y
            if (!mp2.count(x) || x == y) continue; //如果没有数字映射为x或者x等于y，则跳过这次操作
            if (!mp2.count(y)){ //如果当前还没有任何数字映射成y
                mp1[mp2[x]] = y; //将映射为x的集合映射为y
                mp2[y] = mp2[x]; 
                mp2.erase(x); //注意删边
            }
            else {
                join(mp2[x], mp2[y]); //如果已经有集合映射为y了，我们将这两个集合进行合并
                mp1.erase(mp2[x]);
                mp2.erase(x);
            }
        }
        for (int i = 1; i <= n; i++){
            cout << mp1[_find(a[i])] << ' '; //最后直接找到这个元素所在的集合，并输出这个集合映射到的元素即可 
        }
        cout << endl;
    }
    return 0;
}