【基本数据结构】并查集-C++

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受;即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果，只能用并查集来描述。

并查集是一种树型的数据结构，用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。

摘自网络↑

下面主要是自己的感悟emm可能有些不对的地方欢迎指出

并查集，顾名思义，方便的主要就是合并和查询两种基本操作，然后说一下并查集的基本操作：

fa[i]表示点i的父节点，根节点的父节点是它自己。

这里就涉及到初始化，因为开始的时候每一个点都是一棵独立的树，它们都是根节点，所以它们要把fa[i]=i。

另外sz[i]表示这一棵树的深度，只有根节点的sz值才是有效的，可能有些题目里不会涉及但是还是打上来哈

void init()

{

  	for(int i=1;i<=n;i++)

  	{

    	fa[i]=i;

    	sz[i]=1;

    }

}

合并：

在实现合并操作之前，我们先要想一个问题：合并两棵树，是不是把这两棵树上任意两个节点产生联系就可以了？

很明显不是。

我们的合并操作，应该是要把其中一整棵树都挂在另一棵树的根节点上，也就是把a树的根节点的父节点设置为b树的根节点，就完成了a,b两树的合并。

所以现在的问题是取根节点。

初始写法：

int get(int x)

{

  	if(fa[x]==x)

  		return x;

  	return get(fa[x]);

}

但是！如果这么写，每次查找根节点都要花费太多的时间，如果题目特殊构造一条链型的树，那么就会出现TLE.

怎么优化呢？

其实，在每次查找根节点所途径的路上遇到的所有节点，我们都可以把它们直接挂到根节点上，这样下次查找的时候就会方便许多了。

最终写法：

int get(int x)

{

  	if(fa[x]==x)

  		return x;

  	int r=get(fa[x]);

  	fa[x]=r;

  	return r;

}

那么接下来才是实现合并的操作。

所谓合并，就是如上所述，把其中一棵树的根节点挂到另一棵树的根节点上，实现合并，那么就很容易实现：

void merge(int x,int y)

{

  	int r1=get(x);

	int r2=get(y);

	if(r1==r2)

		return;

	fa[r1]=r2;

	sz[r2]+=sz[r1];

}

sz数组的变化请自行理解（绝对不是懒得写）

下一个，查找。

查找其实很简单，就是看两个节点的根节点是否相同，如果一样，那么就是在同一棵树上，否则就不是：

bool ask(int x,int y)

{

	if(get(x)==get(y))return true;

	else return false;

}

下面贴上完整代码：

#include<bits/stdc++.h>

using namespace std;

int n,fa[10001],z,x,y,m,sz[10001];

void init()

{

  	for(int i=1;i<=n;i++)

  	{

    	fa[i]=i;

    	sz[i]=1;

    }

}

int get(int x)

{

  	if(fa[x]==x)

  		return x;

  	int r=get(fa[x]);

  	fa[x]=r;

  	return r;

}

void merge(int x,int y)

{

  	int r1=get(x);

	int r2=get(y);

	if(r1==r2)

		return;

	fa[r1]=r2;

	sz[r2]+=sz[r1];

}

bool ask(int x,int y)

{

	if(get(x)==get(y))return true;

	else return false;

}

int main()

{

	cin>>n>>m;

	int fa[n];

	init();

	for(int i=1;i<=m;i++)

	{

		cin>>z>>x>>y;

		if(z==1)

		{

			merge(x,y);

		}

		else

			if(ask(x,y))cout<<"Y"<<endl;

			else cout<<"N"<<endl;

	}

	return 0;

}

ov.

巴特西

【基本数据结构】并查集-C++

最新文章

热门文章