首页 > 其他分享 >并查集

并查集

时间:2023-02-05 00:45:45浏览次数:56  
标签:查集 int 元素 Find fa 节点

并查集

并查集基础

定义

并查集是一种树型的数据结构,主要用于处理一些不相交集合的合并及查询问题(即所谓的并、查)。一些常见的用途有连通子图、最小生成树的Kruskal算法和求最近公共祖先等。

并查集的实现与优化

并查集的原理:

  • 每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的父节点,pre[x]表示x的父节点。
  • 如果x为树根的话,pre[x]=x (x的父节点指向自己)
  • 求x的集合编号(x的祖宗节点):while(pre!= x ) x = pre[x];
  • 合并两个集合,将x的根节点嫁接到y的根节点,如:prex是x的集合编号,prey是y的集合编号,嫁接:pre[prex]= prey;

代码实现

int f[maxn]; //全名为 father,父节点的意思

//初始化 n个元素
void Init()
{
    //使每个元素的根节点是其本身
    //即初始时每个元素都是单独的
    for(int i=1; i<=n; i++)
        f[i]=i;
}
//查询树的根
//非递归实现
int Find(int i)
{
	while(f[i] != i)   //直到元素的父节点是它本身,表示已经查询到了树的根
		i = f[i];
	return i; 			//返回根节点对应的元素
}

//递归实现
int Find(int i)
{
	if(f[i]==i)      //若元素的根节点为其本身,那么此元素就是树的根
		return f[i];    //直接返回元素本身即可
	else
		return Find(f[i]); //否则继续查询,知道查询到树的根位置
}

//简化版
int Find(int i)
{
	return f[i]==i ? f[i] : Find(f[i]);
}
//合并
void merge(int a, int b)
{
	//先找到两个元素对应的根对应的元素
	int fa = Find(a);
	int fb = Find(b);
	if(fa==fb) return;
	else f[fa]=fb;  //否则令元素 a的根指向元素 b的根
}

//简化版
void merge(int a, int b)
{
	f[Find(a)] = Find(b);
}

代码优化

优化1:按秩合并

首先,我们合并时,可记录这棵树的高度(记为rank)。接下来当我们需合并两棵树时,我们先对两棵树的高度进行判断,如不同,则让高度小的树的根指向高度大的根。

//初始化优化
int f[maxn];
int h[maxn]; //全名为 height

void Init()
{
	for(int i=1; i<=n; i++)
    {
		f[i] = i;
		h[i] = 0;  //令每棵树的高度初始值都为 0
	}
}
//合并优化
void merge(int a, int b)
{
	int fa = Find(a);
	int fb = Find(b);
	if(fa==fb) return;

	if(h[fa] < h[fb])
    {  //如果元素 a对应的树的高度比 b小
		f[fa] = fb;  //使元素 a的根指向元素 b的根
	}
    else
    {
		f[fb] = fa;  //否则让元素 b的根指向元素 a的根
		if(h[fa] == h[fb]) h[fa]++;
		// 如果两者对应的树的高度相同,则使新生成的树高度 +1
	}
}

优化2:路径压缩

由于查询时我们需沿着元素所在的树从下往上查询,最终找到这棵树的根,表明这个元素与其根对应元素属于同一组。因为在此查询过程中我们会经过许多节点,而如果我们能将这个元素直接指向根节点,那么就能节省许多查询的时间。同时,在查询过程中,每次经过的节点,我们都可以同时将他们一起直接指向根节点。这样做的话,我们再查询这些节点时,就能很快知道他们的根是谁了。

//查询优化
int Find(int i)
{
	return f[i]==i ? f[i] : f[i] = Find(f[i]);
	//使元素直接指向树的根
}

最终代码实现

void Init()
{
	for(int i=0; i<=n; i++)
    {
		f[i] = i;
		h[i] = 0;
	}
}
int Find(int i)
{
	return f[i]==i ? f[i] : f[i]=Find(f[i]);
}
void merge(int a, int b)
{
	int fa = Find(a);
	int fb = Find(b);
	if(fa != fb)
    {
		if(h[fa] < h[fb])
        {
			f[fa] = fb;
		}
        else
        {
			f[fb] = fa;
			if(h[fa] == h[fb]) h[fa]++;
		}
	}
}

并查集入门模板题

https://blog.csdn.net/weixin_51250927/article/details/113621645

并查集进阶

带权并查集

定义:

带权是指一个元素具有额外的信息。比如元素1对应着数值6,元素2对应着数值4。这些带有信息的元素组成的并查集即为带权并查集。

作用:

带权并查集能计算各个小组中元素的个数、能计算n个元素中还有几个元素没有加入小组中;计算分数、距离等等

注释:带权并查集需要在路径优化的基础下进行。

带权并查集模板题:

https://blog.csdn.net/weixin_51250927/article/details/113620822

种类并查集

定义;

种类并查集是能把并查集分为几个部分,每个部分的种类不同。

作用:

种类并查集能将两个阵容分开。比如把好人和坏人分为两个阵营。

https://blog.csdn.net/weixin_51250927/article/details/113617248

https://blog.csdn.net/weixin_51250927/article/details/113619285

标签:查集,int,元素,Find,fa,节点
From: https://www.cnblogs.com/coto/p/17092716.html

相关文章

  • 并查集
    ATC(ABC287CPathGraph?)#include<bits/stdc++.h>usingnamespacestd;structDSU{vector<int>f,siz;DSU(intn):f(n),siz(n,1){iota(f.begin()......
  • 并查集
    并查集属于图的知识,一般应用于给出几组关系,来判断谁和谁是一个团队的。先来看一个实例,​​杭电1232畅通工程​​ 首先在地图上给你若干个城镇,这些城镇都可以看作点,然后告......
  • POJ 2492 A Bug's Life(并查集)
    DescriptionBackgroundProfessorHopperisresearchingthesexualbehaviorofararespeciesofbugs.Heassumesthattheyfeaturetwodifferentgendersandthat......
  • POJ 1182 食物链(并查集)
    Description动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B,B吃C,C吃A。 现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是......
  • ZOJ 3261 Connections in Galaxy War (并查集+离线处理)
    Description:Inordertostrengthenthedefenseability,manystarsingalaxyalliedtogetherandbuiltmanybidirectionaltunnelstoexchangemessages.However,......
  • POJ 1733 Parity game (路径压缩并查集+离散化)
    DescriptionNowandthenyouplaythefollowinggamewithyourfriend.Yourfriendwritesdownasequenceconsistingofzeroesandones.Youchooseacontinuous......
  • POJ 2253 Frogger(并查集+二分||Dijkstra)
    DescriptionFreddyFrogissittingonastoneinthemiddleofalake.SuddenlyhenoticesFionaFrogwhoissittingonanotherstone.Heplanstovisither,but......
  • POJ 1456 Supermarket (贪心+并查集优化)
    DescriptionAsupermarkethasasetProdofproductsonsale.Itearnsaprofitpxforeachproductx∈Prodsoldbyadeadlinedxthatismeasuredasanintegral......
  • 数据结构——并查集
    一、并查集的概念在计算机科学中,并查集是一种树形的数据结构,用于处理不交集的合并(union)及查询(find)问题。 并查集可用于查询网络中两个节点的状态,这里的网络是......
  • 【新生寒训】day 24 并查集 ST表与RMQ
    【新生寒训】day24并查集ST表与RMQ记得看看这个( ̄▽ ̄)"一些方法论:https://www.cnblogs.com/CTing/p/17067404.html今日小题https://atcoder.jp/contests/abc132/tasks/......