默认大家都会并查集了

1.题目

小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。

现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？

事件共有 2 种：

1 u v：代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。

2 u v：代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。

注：介绍可以有多层，比如 2 号把 1 号介绍给 3 号，然后 3 号再把 1 号介绍给 4 号，这样 1 号和 4 号就认识了。

输入描述

第一行输入三个正整数n,m,q，代表总人数，初始的朋友关系数量，发生的事件数量。接下来的m行，每行输入两个正整数u,v，代表初始编号u的人和编号v的人是朋友关系。接下来的q行，每行输入三个正整数op,u,v，含义如题目描述所述。

2.思路

显然，查找公共祖先的很容易就能想到并查集的数据结构
但并查集因为将子节点到祖先节点的边压缩了，所以我们并不好维护边的删除，所以采用反向建立并查集

3.代码

#include<bits/stdc++.h>
using namespace std;const int N = 100007;
int p[N], n, m, q;int find(int x){if(p[x] != x) p[x] = find(p[x]);return p[x];
}void merge(int x, int y){int px = find(x), py = find(y);if(px != py) p[px] = py;
}
int main(){set<pair<int, int>> edges, del_edges;cin >> n >> m >> q;for(int i = 1; i <= n; i++) p[i] = i;for(int i = 1; i <= m; i++){int u, v;cin >> u >> v;edges.insert({u, v});}vector<vector<int>> queries(q);for (int i = 0; i < q; i++) {int op, u, v;cin >> op >> u >> v;queries[i] = {op, u, v};if (op == 1) {del_edges.insert({u, v});}}for (auto &[u, v] : edges) {if (del_edges.find({u, v}) == del_edges.end() && del_edges.find({v, u}) == del_edges.end()) {merge(u, v);}}vector<string> ans;for (int i = q - 1; i >= 0; i--) {int op = queries[i][0];int u = queries[i][1];int v = queries[i][2];if (op == 2) {if (find(u) == find(v)) ans.push_back("Yes");else ans.push_back("No");} else {merge(u, v);}}reverse(ans.begin(), ans.end());for(auto s : ans){cout << s << endl;}return 0;
}