这是一个并查集模板。
说一下并查集，虽然我也是刚刚学会没几天。。。
并查集是个树形结构的数据结构，主要用于合并两个不相交的集合；
首先是初始化,其中的f数组表示第i点的父亲
for(int i=1;i<=n;i++)f[i] = i;
并查集分为合并与查询，我习惯写成merge（合并)，query（查询）
合并的话,首先调用query函数去查询两点的祖先节点，如果不是同一祖先，两个集合就没有关联，然后就将其祖先节点所代表的集合合并，（我所用的rand是让合并的方向打乱，不易被卡），好像还有按秩合并，然而我还不会，以后再补这个锅吧，，，
void merge(int x,int y){
int f1 = query(x);
int f2 = query(y);
if(f1 != f2){
if(rand()%2)f[f1] = f2;
else f[f2] = f1;
}
return;
}
接下来就是query（查询操作），不断递归查询父亲节点，直到找到祖先节点，后面的是路径压缩，因为寻找路途上的所有点的祖先节点相同，所以在返回的时候把每个点去都放入同一集合，可以极大的缩短查询时间，写并查集的话一定带上路径压缩，不然会被卡。不过好像有卡路径压缩的题，只是听dalao说过，具体问题具体分析吧。
int query(int x){
if(x == f[x])return x;
else return f[x] = query(f[x]);//路径压缩
}
下面是这道题，就是一个并查集根据题目要求做就可以了
题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
题目描述
规定：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个询问的答案为“具有”或“不具有”亲戚关系。
输入输出样例
输入样例#1： 复制
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
输出样例#1： 复制
Yes
Yes
No
附AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxn = 500521;
int n,m,p;
int mi;
int mj;
int pi;
int pj;
int f[maxn];
inline int read(){//读入优化
int x=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-f;
c=getchar();
}
while(c<='9'&&c>='0'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int query(int x){//查询操作
if(x == f[x])return x;
else return f[x] = query(f[x]);//路径压缩
}
void merge(int x,int y){//合并操作
int f1 = query(x);
int f2 = query(y);
if(f1 != f2){
if(rand()%2)f[f1] = f2;
else f[f2] = f1;
}
return;
}
int main(){
n = read();
m = read();
p = read();
for(int i=1;i<=n;i++)f[i] = i;//初始化，不能丢
for(int i=1;i<=m;i++){
mi = read();
mj = read();
merge(mi,mj);
}
for(int i=1;i<=p;i++){
pi = read();
pj = read();
if(query(pi) == query(pj)){
printf("Yes\n");
}
else printf("No\n");
}
return 0;
}
网友评论