1073 家族（并查集模板）

﹏ヽ暗。殇╰゛Y 2022-06-15 00:37 164阅读 0赞

题目描述 Description

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

6 5 3

1 2

1 5

3 4

5 2

1 3

1 4

2 3

5 6

样例输出 Sample Output

Yes

Yes

No

数据范围及提示 Data Size & Hint

n<=5000,m<=5000,p<=5000

#include<iostream>
    #include<string.h>
    #include<cstdio> 
    using namespace std;
    int pre[30000];
    int n,m,p;
    void init()
    {
    	for (int i=1; i<=n; i++)
    	{
    		pre[i] = -1; 
    	} 
    }
    int find(int num)
    {
    	while (pre[num]>-1)
    	{
    		num = pre[num];
    	}
    	return num;
    }
    void union_set(int x, int y)
    {
    	int xx = find(x);
    	int yy = find(y);
    	if (xx != yy)
    	{
    		pre[xx] += pre[yy];
    		pre[yy] = xx;
    	}
    }
    int main()
    {
    	scanf("%d%d%d",&n,&m,&p); 
    	init();
    	int x, y;
    	while (m--)
    	{
    		scanf("%d%d",&x,&y);
    		union_set(x,y);
    	}
    	while (p--)
    	{
    		scanf("%d%d",&x,&y);
    		 if (find(x) == find(y))
    		 {
    		 	cout<<"Yes"<<endl;
    		 }else{
    		 	cout<<"No"<<endl; 
    		 }
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，164人围观）

还没有评论，来说两句吧...

相关阅读

相关并查集(模板)

并查集(模板) [来源][Link 1] 并查集：将不同分散的结点，通过某种关系将他们连接成一个森林并查集分为3步： 1. 并：给出两点关系，如果属于同

蔚落/ 2023年06月01日 06:11/ 0 赞/ 21 阅读

相关 Vijos P1034家族【基础并查集】

P1034家族未递交标签： \[显示标签\] 描述若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否

清疚/ 2022年08月18日 02:12/ 0 赞/ 137 阅读

相关并查集&&最小生成树（模板）

并查集 int find(int x){ //查查找根节点 int r=x; while(r!=pre[r]) r

小灰灰/ 2022年08月03日 15:53/ 0 赞/ 187 阅读

相关 1073 家族（并查集模板）

题目描述 Description 若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲

﹏ヽ暗。殇╰゛Y/ 2022年06月15日 00:37/ 0 赞/ 165 阅读

相关模板--并查集

问题描述： Mr Wang wants some boys to help him with a project. Because the project is ra

雨点打透心脏的1/2处/ 2022年06月11日 04:21/ 0 赞/ 198 阅读

相关并查集

> 题目 > 某学校近期要组织全校同学出去参加某项活动，由于人数众多，学校决定让同学们自行组队，以小组为单位进行活动。假设学校一共n个同学，每个同学有一个唯一的数字作为标签

Myth丶恋晨/ 2022年06月08日 09:24/ 0 赞/ 320 阅读

相关并查集

森林: 森林是由若干棵互不相交的树组成,两棵树分别独立,没有交集 ![20181112082744488.png][] 并查集: 并查集的结构和森林十分相似,是

Love The Way You Lie/ 2022年04月17日 02:27/ 0 赞/ 379 阅读

相关并查集

来看一个实例，[杭电1232畅通工程][1232] 首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性

我就是我/ 2022年03月29日 10:58/ 0 赞/ 384 阅读

相关【codevs1073/P1551】家族/亲戚——并查集

题目链接：[codevs][]，[洛谷][Link 1] -------------------- 这道题就是并查集的基础题，getf函数寻找该节点的祖先

Myth丶恋晨/ 2021年09月30日 16:30/ 0 赞/ 248 阅读

相关并查集模板超详细整理

并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作： ·合并（Union）：把两个不相交的集合

阳光穿透心脏的1/2处/ 2021年08月30日 01:53/ 0 赞/ 465 阅读