并查集的经典例题(一)

不念不忘少年蓝@ 2023-03-01 12:26 1阅读 0赞

# 例题：亲戚 #

## 题目背景： ##

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

## 题目描述： ##

规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

## 输入格式： ##

第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。  
以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。  
接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。

## 输出格式 ##

P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

## 输入输出样例 ##

输入：  
6 5 3  
1 2  
1 5  
3 4  
5 2  
1 3  
1 4  
2 3  
5 6  
输出：  
Yes  
Yes  
No

## 解题思路 ##

这是一道标准的并查集例题，十分适合新手入门练习。根据题意，将两个具有亲戚关系的人组合起来，形成并查集，然后在并查集中查找。

## 解题代码 ##

#include<iostream>
    using namespace std;
    int n,m,p,pre[1000];
    //寻找两个元素之间是否是亲戚关系
    int find(int x){
        
    	if(pre[x] == x) return x;
    	else{
        
    		pre[x] = find(pre[x]);
    		return pre[x];
    	}
    }
    //连接两个具有亲戚关系的元素
    void merge(int x,int y){
        			
    	pre[find(y)] = find(x);
    	return;
    }
    int main(){
        
    	int x,y;
    	int a,b;
    	cin>>n>>m>>p;
    	//构成并查集，此时并查集中的每个元素的亲戚（根节点）就是其本身
    	for(int i = 1;i <= m;++i){
        			
    		pre[i] = i;
    	}
    	
    	for(int i = 1;i <= m;++i){
        
    		cin>>x>>y;
    		merge(x,y);						
    	}
    	for(int i = 1;i <= p;++i){
        
    		cin>>a>>b;
    		if(find(a) == find(b))	cout<<"yes"<<endl;
    		else cout<<"no"<<endl;
    	}
    	return 0;
    }