首页 > 其他分享 >并查集

并查集

时间:2023-02-23 15:55:59浏览次数:40  
标签:di int 查集 亲戚 节点 Yes find

并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合,并支持两种操作:

  • 合并(Union):把两个不相交的集合合并为一个集合。
  • 查询(Find):查询两个元素是否在同一个集合中。

例题:亲戚

或许你并不知道,你的某个朋友是你的亲戚。
他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。
如果能得到完整的家谱,判断两个人是否是亲戚应该是可行的,但如果两个人的最近公共祖先与他们相隔好几代,使得家谱十分庞大,那么检验亲戚关系实非人力所能及。
在这种情况下,最好的帮手就是计算机。
为了将问题简化,你将得到一些亲戚关系的信息,如Marry和Tom是亲戚,Tom和Ben是亲戚,等等。
从这些信息中,你可以推出Marry和Ben是亲戚。
请写一个程序,对于我们的关于亲戚关系的提问,以最快的速度给出答案。

输入格式

输入由两部分组成。
第一部分以 N,M 开始。N 为问题涉及的人的个数。这些人的编号为 1,2,3,…,N。下面有 M 行,每行有两个数 ai,bi,表示已知 ai 和 bi 是亲戚。
第二部分以 Q 开始。以下 Q 行有 Q 个询问,每行为 ci,di,表示询问 ci 和 di 是否为亲戚。

输出格式

对于每个询问 ci,di,输出一行:若 ci 和 di 为亲戚,则输出“Yes”,否则输出“No”。

数据范围

1≤N≤20000,
1≤M≤106,
1≤Q≤106

输入样例:

10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9

输出样例:

Yes
No
Yes

代码

#include<iostream>

using namespace std;

int p[20010];
//查询祖宗节点:一层一层访问父节点,直至根节点(根节点的父节点就是自己)。要判断两个元素是否属于同一个集合,只需要看它们的根节点是否相同即可。
int find(int x) {//查询+路径压缩
	if (p[x]!=x) p[x] = find(p[x]);
	return p[x];
}

int main() {
	int n, m;
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i++) p[i] = i;//用一个数组p[]来存储每个元素的父节点(因为每个元素有且只有一个父节点)。一开始,我们先将它们的父节点设为自己。
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d%d",&a,&b);
		if (find(a) != find(b)) 
		p[find(b)] = find(a);//合并:先找到两个集合的祖宗节点,然后将前者的父节点设为后者
	}
	int q;
	scanf("%d",&q);
	while (q--) {
		int c, d;
		cin >> c >> d;
		if(find(c) == find(d)) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

标签:di,int,查集,亲戚,节点,Yes,find
From: https://www.cnblogs.com/wustRen/p/17148314.html

相关文章

  • 并查集
    并查集序言:我们大家都是好朋友并查集是一种维护关系的数据结构新手所学的并查集都是维护朋友关系的并查集朋友的朋友是朋友我们可以将变成朋友的点连到同一个集合中......
  • 浅谈一类多重传递关系的并查集问题
    首先解释一下什么叫“多种传递关系”:普通的并查集只能维护“朋友的朋友是朋友”,而面临“敌人的敌人是朋友”的情况十分乏力,多种传递关系即指“敌人的敌人是朋友”类情况。......
  • A - 并查集【2022级专题三图论课后练习】
    A-并查集思路模板注意01串的处理代码点击查看代码#include<iostream>usingnamespacestd;#defineXfirst#defineYsecondtypedefpair<int,int>pii;......
  • 【DFS&并查集】岛屿数量
    经典的dfs/bfs问题,给一个起点开始搜索,满足条件则继续调用dfs/bfs从没有访问过的某个陆地出发,将所有能到达的陆地的状态都记录为已访问。下次出发不从已访问的陆地出发,每次......
  • C - Roads and Libraries HackerRank - torque-and-development 【 并查集 】
    C-RoadsandLibraries HackerRank-torque-and-development 题意:给一堆点与点之间有没有边,在某一些地方建图书馆,最后让每个城市都可以到达有图书馆的地方,每个点......
  • Codeforces Round #851 (Div. 2)-F. XOR, Tree, and Queries-树、异或、并查集
    题目:https://codeforces.com/contest/1788/problem/F题解:(首先他和线性基没什么瓜系)想这个问题大概可以分成几个部分:1、很自然地考虑记\(p_x\)表示从根节点走到x路径......
  • 「AcWing学习记录」并查集
    并查集1.将两个集合合并2.询问两个元素是否在一个集合当中时间复杂度近乎O(1)基本原理每个集合用一棵树来表示。树根的编号就是整个集合的编号,每个节点存储它的父节点......
  • 并查集
    一、什么是并查集什么是并查集?字面意思把一堆东西  合并  、  查找二、并查集讲解前置知识点1.可以把并查集的实现理解为在合并几棵树2.需要用到fa数组,fa[i......
  • 并查集
    并查集大佬笔记如下:通俗易懂https://zhuanlan.zhihu.com/p/93647900并查集是什么?主要用于解决一些元素分组的问题。它管理一系列不相交的集合,并支持两种操作:合并:把......
  • 【YBT2023寒假Day8 C】图论题(图论)(并查集)(线段树合并)
    图论题题目链接:YBT2023寒假Day8C题目大意给你一个无向图,然后你会一直操作直到无法操作,每次找出一个满足条件的三元组(a,b,c),满足a<b<c,a,b与a,c之间有边,b,c之间没......