洛谷 P1551 题解

题目背景

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

题目描述

规定：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; }