并查集（C++）

最近也是被数论搞的头大，不得不说，数学YYDS；

然后我立马拥抱了并查集，哈哈哈。

话不多少，卷起来。

可能之前没有了解过并查集的小伙伴感觉并查集很高级，的确这个名字的确很高级，不过今天就让我们来揭开这个神秘的数据结构。

没错，并查集就是一种树形的数据结构，看它的名字，合并 和 查询 。

 所以它支持两种操作：

查找：确定某个元素处于哪个子集。

合并：将两个子集进行合并。

 下面，我们来初步了解一下并查集的应用场景：

几个家族在一起聚会，我们只知道两个人的关系，然后给出两个人判断他们是否是一个家族的。我们知道每个家族肯定有一个长者，也就是祖先，我们只需要判断两个人的祖先是不是同一个就可以知道两个人是不是一个家族的了。

我们来看一个例子：

 我们要查看4 7 是不是一个家族，我们只需要查看4 7 的祖先是不是一个人即可。

int p[N];
int find(int x)
{
	if(p[x] == x)return x; //如果自己就是祖先的话，返回自己。
	else return find(p[x]); // 自己不是祖先的话，寻找自己的祖先。
} 

但是这样一个一个的查太慢了。所以我们想到了一个这样的办法，路径压缩。

我们只需要知道某个人的祖先是谁就好了，我们跨过其他点，直接连到祖先上。

int find(int x)
{
	if(p[x] != x) p[x] = find(p[x]); //如果x自己不是祖先的话，让p[x] = 祖先
	return p[x]; 
}

 我们再来看看合并，如何合并两个子集：

 我们只需要让一个子集的祖先指向另一个子集的祖先即可，这么举例不是很恰当，但是原理就是这样的，我们就把两个集合合并了。

接下来我们来看两个例题吧：

【模板】并查集 - 洛谷

加一点点难度：朋友 - 洛谷

#include
using namespace std;

const int N = 500010;

typedef long long LL;


int p[N]; 

int find(int x)
{
	if(p[x] != x) p[x] = find(p[x]);
	return p[x]; 
}

int n,m;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	
	for(int i=0;i>z>>x>>y;
		
		if(z == 1) 
		{
			if(find(x) == find(y))continue;
			p[find(x)] = find(y);
		}
		else
		{
			if(find(x) == find(y))puts("Y");
			else puts("N");
		}
	}
	
	
	
	return 0;
} 

get！