题目： 传送门
大意： 有1 ~ n个人，现给定若干数对（x，y），表示x和y有亲戚关系。同时，关系具有传递性，即x和y有关，y和z有关，就会有x和z有关。现在要判断给出的若干数对的相关性，输出Yes或No
思路： 使用并查集，也就是把有关系的数字放到若干个集合中，并从这些集合中随便选取一个数作为这个集合的标志，每个数 i 的标志保存在 pre[i] 数组中，于是查询时，只要看a和b所属集合的标志是否相同即可。由于合并集合A和B时，是直接把集合B的标志改为集合A里面的一个元素，故在查询元素是否属于A ∩ B时，需要递归地更新元素（见代码）
Code：
#include<bits/stdc++.h>typedef long long ll;
using namespace std;
const int maxn = 5007;
struct node {int n, m, q, pre[maxn];//pre[i]记录i的标志int rk[maxn];//rk[i]记录以i为根的树的深度void init(int nn, int mm, int qq) {n = nn;m = mm;q = qq;for (int i=1;i<=n;i++) {//刚开始每个人的标志就是自己pre[i] = i;rk[i] = 1;}}int find(int x) {//查找x的标志,由于merge操作是直接把fx接在fy上,可能导致属于同一集合,但两个元素标志不一致的情况,所以要递归地更新标志,保证一致if (x == pre[x]) return x;//标志就是自己的情况return pre[x] = find(pre[x]);//把x的标志更新为pre[x]的标志}void merge(int x, int y) {//把x和y所属的集合合并x = find(x);y = find(y);//分别找x和y所属集合的标志(已进行统一)//if (fx != fy) pre[fx] = fy;//如果标志不一样,把fx接在(这里的“接”是把集合看成了多叉树森林中两棵树的合并)fy上,也可以pre[fy] = fx;//以下是考虑了树的高度后进行合并if (rk[x] < rk[y]) {//x所在的树较矮,那么就把x“接”到y上pre[x] = y;} else {pre[y] = x;if (rk[x] == rk[y]) rk[x]++;//如果x,y所在的树一样深,接在一起的时候,深度要+1}}void get_relation() {//获取关系int x, y;for (int i=1;i<=m;i++) {cin>>x>>y;merge(x, y);}}void print_query() {//判断有无关系int x, y;for (int i=1;i<=q;i++) {cin>>x>>y;if (find(x) == find(y))cout<<"Yes"<<endl;elsecout<<"No"<<endl;}}
};
int main()
{int n, m, p;cin>>n>>m>>p;node nd;nd.init(n, m, p);nd.get_relation();nd.print_query();return 0;
}