Java教程

并查集基础学习笔记

本文主要是介绍并查集基础学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

并查集的定义(百度搜索):

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


1.初始化

设立一个数组f,f[i]表示i的大哥,初始化时把i的大哥定为自身.

for(i=1;i<=n;i++)f[i]=i;//初始化


2.查询

找到x最大的大哥,我这里称为老大.

通过递归的方式来查询,如果一个人的大哥是自己,他就是这棵树里的根.

int find(int x){
  if(f[x]==x)return x;//递归边界,判断自己是不是老大.    
  return find(f[x]);//通过递归调用,x的大哥的大哥......,直到找到是老大为止.
}//找到x的老大

考虑一下当树为一条链的时候,查询的时间复杂度便达到了o(n),考虑优化.

于是便有了路径压缩:

假设有三个人小甲,小乙,小丁.

小甲是小乙的大哥,小乙是小丁的大哥,那么实则小甲就是小丁的老大.

现在不管谁的大哥是谁,只关心谁的老大是谁,那么就可以进行如下优化:

int find(int x){
  if(f[x]==x)return x;    
  return f[x]=find(f[x]);
  /*
     也就是:
     f[x]=find(f[x]);
     return f[x];
  */
}//找到x的老大

此时进行完x的查询后,他以及他的大哥一直到他的老大的f数组都更新为x的老大.也就是把下图的f[5],[4],f[3],f[2],f[1]都改为f[1].f数组此时指向的便是x这条路径上的经过元素的老大了。但此时树只有两层,大哥也就是老大,所以f数组的含义也就是大哥,与原来一样.

 优化后树只有两层.



3.合并

没什么好解释的,也就是把x的老大的大哥(f[find(x)])赋值为y的老大,把x的帮派直接合并与y的帮派.f[find[x]]=find(y).

.代码如下:

int a=find(x);//x的老大
int b=find(y);//y的老大
f[a]=b;//把y的老大当成x的老大的大哥
/*
  但由于前面路径压缩,不存在大哥(可以理解一棵树包括
  根结点一共有2层,第一层是所有人的老大,第
  二层的人之间没有大哥和小弟这层关系,他们的老大是共同的且只有一个)
*/


题目练习:P3367

这篇关于并查集基础学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!