luogu P1551 亲戚(并查集入门)

这是一个并查集模板。

说一下并查集，虽然我也是刚刚学会没几天。。。

并查集是个树形结构的数据结构，主要用于合并两个不相交的集合；

首先是初始化,其中的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

附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;
}

最后编辑于：2018.08.09 14:24:29