DATA STRUCTURE September 10, 2019

并查集详解

Words count 1.7k Reading time 2 mins. Read count 0

概述

并查集这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大.

并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合,也就是按一定顺序将属于同一组的元素所在的集合合并。

我们关心的是,对于给定的元素,可以很快的找到这个元素所在的集合,我们用祖先代表来描述,以及合并两个元素所在的集合,这些操作都是O(n)的。

其中每个根节点,它的父亲节点为它自己,比如以下就是合并效果。而左边的两个树就是两个集合,并查集的深意就是合并&查找集合的一个操作。

操作

查找根

我们先说一说集合的代表,递归遍历一个树的任意结点,直到走到一个结点它的父亲结点是它自己时

d - b - a

按此顺序遍历其中的一个结点,直到找到它的祖先结点。

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

合并

合并时考虑路径压缩加上路径压缩就会去掉很多不需要的时间成本。

路径压缩的原理就是:

使一个结点的父亲结点作为整个集合的根结点的儿子

如上图

将两个集合合并成一个大的集合,被合并的集合的代表消失,其代表为总代表,即图中的a结点。

void union_Set(int x,int y){
  if((x=find(x))==(y=find(y))) return;
  if(rank[x]>rank[y]) uset[y]=x;
  else{
    uset[x]=y;
    if(rank[x]==rank[y]) rank[y]++;
  }
}
0%