【蓝桥杯集训】Acwing1249.亲戚

1. 题目内容

2. 解题重点

并查集，将有关系的群体融合在一起。为有关系的亲戚设立一个“头头”，如果你的“头头”和我的“头头”一样，则说明我们是一家人。假如给的条件中发现两个头头不同的人也是一家人，那就让其中一家人的头头认另一家的头头为新的头头。

3.答案

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
const int N=20010;
 
int n,m;
int p[N];
 
//找头头
int find(int x){
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}
 
int main(){
    scanf("%d%d",&n,&m);
   //设立头头
    for(int i=1;i<=n;i++){
    	p[i]=i;
	}
//根据关系设立新的头头
	while(m--){
		int a,b;
		scanf("%d%d",&a,&b);
		p[find(a)]=find(b);
	}
	
	scanf("%d",&m);
//判断是不是一家人
	while(m--){
		int a,b;
		scanf("%d%d",&a,&b);
		if(find(a)==find(b))
		puts("Yes");
		else
		puts("No") ;
	}
	
    return 0;
}