题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
题目描述
规定：x 和 y 是亲戚，y 和 z 是亲戚，那么 x 和 z 也是亲戚。如果 x，y 是亲戚，那么 x 的亲戚都是 y 的亲戚，y 的亲戚也都是 x 的亲戚。
输入格式
第一行：三个整数 n,m,p，（n,m,p≤5000），分别表示有 n 个人，m 个亲戚关系，询问 p 对亲戚关系。
以下 m 行：每行两个数 Mi，Mj，1≤Mi, Mj≤n，表示 Mi 和 Mj 具有亲戚关系。
接下来 p 行：每行两个数 Pi,Pj，询问 Pi 和 Pj 是否具有亲戚关系。
输出格式
p 行，每行一个Yes或No。表示第 i 个询问的答案为“具有”或“不具有”亲戚关系。
输入输出样例
输入 #1复制
6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6
输出 #1复制
Yes Yes No
一道相当接近模板题的并查集。
如果我们注意到并查集是递归实现的并且具有如下形式：
int find(int n,vector<int>&a){ if(a[n]==n)return n; //找到根节点 return a[n]=find(a[n],a); //查询根节点 }这道题就会非常简单：
只需要先将每个a[i]赋值为i,然后对于每个关系使用：（re[i].first，re[i].second对应两个人）
int _min=min(re[i].first,re[i].second); int _max=max(re[i].first,re[i].second); a[find(_max,a)]=find(_min,a);就可以将关系联通（注意我们每次更改的是关系的根节点），随后对于查询，只要找到两人对应的根节点即可。
代码如下：
#include<bits/stdc++.h> using namespace std; int find(int n,vector<int>&a){ if(a[n]==n)return n; return a[n]=find(a[n],a); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); int n,m,p; cin>>n>>m>>p; vector<int>a(n+1,0); vector<pair<int,int>>re(m+1); stringstream ss; for(int i=1;i<=n;i++)a[i]=i; for(int i=0;i<m;i++){ cin>>re[i].first>>re[i].second; int _min=min(re[i].first,re[i].second); int _max=max(re[i].first,re[i].second); a[find(_max,a)]=find(_min,a); } for(int i=1;i<=n;i++)find(i,a); for(int i=0;i<p;i++){ int q1,q2; cin>>q1>>q2; if(find(q1,a)==find(q2,a))ss<<"Yes"<<"\n"; else ss<<"No"<<"\n"; } cout<<ss.str(); return 0; }
