亲戚(并查集)

亲戚

时间限制：1秒内存限制：128M

题目描述

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

规定：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<bits/stdc++.h>  // 包含常用库
#define ll long long     // 为长整型定义别名
#define N 1000001        // 定义常量 N
using namespace std;

int n,m,p,f[N];  // 定义全局变量

// 并查集中查找根节点的函数
int find(int x){
        if(x==f[x]){  // 如果 x 是根节点
                return x; // 返回 x
        }
        // 路径压缩
        return f[x]=find(f[x]);
}

// 并查集的合并函数
vo unionn(int x,int y){
        x=find(x);  // 查找 x 的根节点
        y=find(y);  // 查找 y 的根节点
        f[x]=y;     // 合并
}

// 主函数
int main(){
        cin>>n>>m>>p;  // 输入 n, m 和 p
        for(int i=1;i<=n;i++){
                f[i]=i;  // 初始化并查集
        }
        // 读取并处理 m 个合并操作
        for(int i=1;i<=m;i++){
                int x,y;
                cin>>x>>y;
                unionn(x,y);
        }
        // 读取并处理 p 个查询
        for(int i=1;i<=p;i++){
                int x,y;
                cin>>x>>y;
                if(find(x)==find(y)){  // 如果 x 和 y 属于同一个集合
                        cout<<"Yes\n";  // 输出 "Yes"
                }else{
                        cout<<"No\n";  // 输出 "No"
                }
        }
        return 0;  // 程序结束
}

这个程序实现了一个基本的并查集数据结构，并用它来解决一些基本的连通性问题。具体来说，它首先读入一个有 n 个元素和 m 次合并操作的集合，然后进行 p 次查询，查看两个元素是否在同一集合中。

亲戚(并查集)

热门文章