并查集介绍

并查集的介绍

使用范围

参看wiki,用于处理一些不交集(Disjoint Sets)的合并及查询问题. 我理解的主要是对于一些集合的并集进行快速的处理和查找。用于对数据进行一些分类这样子。

进行的操作

主要的两个操作为find(int root),和进行合并join(int root1, int root2),这两个操作。
在这之前需要介绍一下并查集使用的数据结构,一般使用一个一维数组来进行操作,pre[x] = y这个的含义表示结点x的祖先为y。在了解了这个之后就能够很好的理解上面的两个操作的写法了。

find操作

顾名思义就是找到一个结点的祖先。

join操作

顾名思义就是将两个集合进行合并,并产生一个祖先

connect操作

这类操作也是可能用到的,即判断两个结点是不是在一个集合中。

 

以上便是并查集的大部分操作,难点在于判断什么时候应使用并查集,并根据题目情景进行一些相应的变化。

练习题

题解为:

 

Leave a Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注

本站所有文章均为原创,若需转载,请注明出处©twn29004 | 陕ICP备 20000896 网站备案号

总访问量:9064353    今日访问量:117    您是今天第:117 个访问者