算法模版-并查集

发布于 2019-10-30  294 次阅读


并查集(Union-Find Set)

小声说,这是一个简单的算法( • ̀ω•́ )✧

目录

并查集的简介

模版代码

例题

说明

并查集简介

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

简单来说就是解决动态连通性问题的一类高效的数据结构(>ω・* )ノ。

模版代码

并查集主要包括3个部分,即初始化(Make_set),合并(Merge),查找(Find)。

初始化:每个结点各自为一个集合,这个时候pnt[x]=x,即此时这个结点就是这个集合的根结点,也就是它本身。
查找:找到x这个元素所在集合的根结点。
合并:将连个元素合并到同一个集合当中,在合并之前,一般要判断是否在同一个集合内。

 

先把代码贴上:

是不是很简单啊ヽ(・ω・´メ)!!!1

优化算法-按秩合并+路径压缩:

按秩合并:即总是将更小的树连接至更大的树上。因为影响运行时间的是树的深度,更小的树添加到更深的树的根上将不会增加秩除非它们的秩相同。在这个算法中,“秩”替代了“深度”同时应用了路径压缩时(见下文)秩将不会与高度相同。单元素的树的秩定义为0,当两棵秩同为r的树联合时,它们的秩r+1。

路径压缩:在查找时压扁树,在查找过程中将查找路径上所有结点都指向根结点,把所有访问过的结点直接链接到根,这样可以减少将来的查找时间。(路径压缩只改变数的高度,不改变数的秩)。

应该很好理解的下面我们来实战一下

例题

先贴上例题位置How Many Tables类似题目还有畅通工程。(`・ω・´)

How Many Tables其实就是一道简单的并查集,只要套模版,然后输出就能AC

题目

Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.

One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.

For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.

Input

The input starts with an integer T(1<=T<=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1<=N,M<=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.

Output

For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.

样例

Sample Input

 

2
5 3
1 2
2 3
4 5
5 1
2 5

Sample Output

2
4
AC代码

说明

并查集其实很简单了,只要背下模版就很容易AC的。那接下来可能会写并查集的衍生-权值并查集(期待ing)。(〃´-ω・) 

如果你喜欢这篇博客,或者对你有一点点的帮助的话,不妨在右下角点个喜欢,让我知道哦(*/ω\*)


Σσ(・Д・;)我我我什么都没做!!!