双重映射+逆向并查集+恢复

本文主要是介绍双重映射+逆向并查集+恢复，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言：一开始没有想着要逆序，自己写了一个并查集但是过了百分之五十，也不知道哪里出了问题

这一题的本质我们要知道，后面的修改覆盖前面的修改，我们直接从后面开始操作就行，然后我们这一题的恢复也是有技巧的

注意逆向操作可以避免环的问题

$12$
$21$
$fa[2]=fa[1]$
$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;
}

这篇关于双重映射+逆向并查集+恢复的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---