双重映射+逆向并查集+恢复
前言：一开始没有想着要逆序，自己写了一个并查集但是过了百分之五十，也不知道哪里出了问题
这一题的本质我们要知道，后面的修改覆盖前面的修改，我们直接从后面开始操作就行，然后我们这一题的恢复也是有技巧的
注意逆向操作可以避免环的问题
12 1 2 12
21 2 1 21
f a [ 2 ] = f a [ 1 ] fa[ 2 ] = fa[ 1 ] fa[2]=fa[1]
f a [ 1 ] = f a [ 2 ] fa[ 1 ] = fa[ 2 ] fa[1]=fa[2]
对我们的结果没有影响
题目地址
#include<bits/stdc++.h>
using namespace std;#define int long longint t;
int n,m;
const int N = (int)1e6+10;
int a[N];
int fa[N];
int u[N],v[N];void solve(){for(int i=1;i<=m;i++){cin >> u[i] >> v[i];}for(int i=m;i;i--){fa[u[i]] = fa[v[i]];}for(int i=1;i<=n;i++){cout << fa[a[i]] << " ";}cout << endl;for(int i=1;i<=m;i++){fa[u[i]] = u[i], fa[v[i]] = v[i];}
}signed main(){cin >> t;for(int i=0;i<N;i++) fa[i] = i;while(t--){cin >> n >> m;for(int i=1;i<=n;i++) cin >> a[i];solve();}return 0;
}