UnionFind
问题描述
在计算机科学中,并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。有一个联合-查找算法(union-find algorithm)定义了两个用于此数据结构的操作:
- $Find$:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
- $Union$:将两个子集合并成同一个集合。
由于支持这两种操作,一个不相交集也常被称为联合-查找数据结构(union-find data structure)或合并-查找集合(merge-find set)。其他的重要方法,MakeSet,用于建立单元素集合。有了这些方法,许多经典的划分问题可以被解决。
为了更加精确的定义这些方法,需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素,称为代表,以表示整个集合。接着,$Find(x)$返回 x 所属集合的代表,而$Union$使用两个集合的代表作为参数。
更进一步的,当两个元素之间的关系可以量化,并且关系可以合并时,可以使用带权并查集来维护元素之间的关系。
带权并查集即是结点存有权值信息的并查集。
算法介绍
问题建模
并查集的本质是一个森林,每棵树代表一个集合,树根为集合的代表元。
我们可以使用有根树来进行建模,对于一个新加入的节点,就将其添加到对应的集合里面去。那么如何维护这个集合关系呢?只需要使得每个节点保存自己父亲节点即可。
但是即便如此,效率也还是不高,因为随着规模的增大,树的深度提高,查找的效率下降严重。所以,每次查找的时候,如果路径较长,则修改信息,以便下次查找的时候速度更快。这就是“路径压缩”的思想。
同时,我们也可以维护一个$rank$值,表示一个树的规模,我们总是把小树合并到大树上面,这样可以有效的降低深度,防止最坏情况的发生。
求解方法
并查集的代码书写十分简单,首先初始情况下,可以把每个点都看成是一个小的集合,通过将$father$数组指定为自己本身来实现。
在$Find$操作中,如果祖宗节点就是自己本身,则可以直接返回;如果不是自己,需要进行递归的操作,具体来说,在计算权值关系的同时,需要将自己合并到自己的祖宗节点之上,通过这个方式可以有效的降低树的深度。
在$Union$操作中,通过比较$rank$来进行合并的操作,可以有效的减少复杂度。
C++代码如下:
|
|
值得一提的是,使用并查集操作,其复杂度为$O(\alpha(n))$,其中$\alpha()$为阿克曼函数的反函数。
解题报告
Poj 1182 食物链
问题描述
动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。
现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述:
第一种说法是”1 X Y”,表示X和Y是同类。
第二种说法是”2 X Y”,表示X吃Y。
此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
1) 当前的话与前面的某些真的话冲突,就是假话;
2) 当前的话中X或Y比N大,就是假话;
3) 当前的话表示X吃X,就是假话。
你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。
Input
第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。
Output
只有一个整数,表示假话的数目。
算法设计
食物链题目是带权并查集的经典题目,首先我们需要明确这里的关系是什么。
根据题目的含义,我们总结出下面三种关系:
关系 | 代表 |
---|---|
和父亲节点同类 | 0 |
被自己的父亲节点吃 | 1 |
吃自己的父亲节点 | 2 |
首先判断数据的规模是否符合题目范围的限制,这个很容易判断。
之后,通过$Find$函数判断这两个点是否在同一个关系集合下面,如果是同一个集合,这里分为两种情况:
是同类
可以直接判断,如果存在“吃”的关系,则说谎数目增加,
否则,将关系纳入并查集中。
存在“吃”或者“被吃”的关系
注意到,这里的食物链其实是一种循环的关系,如图所示:
所以,可以通过取模的关系,进行判断,具体为:$(R_x + d) \% 3\ ==\ R_y$。
如果两者之间没有关系,则需要对关系进行合并,注意合并的时候,一定要分清需要将谁合并到谁,因为这里除了信息给出的新关系,还需要考虑两个节点和各自的祖宗之间的关系,比较复杂。这里给出一个例子:$((3 - R_x) + R_y + d - 1) \ \% \ 3$。
程序代码
|
|
性能分析
由于并查集操作十分的快捷,可以认为其中的每次添加或者查询的时间复杂度是$O(\alpha(n))$级别的,所以最后总的时间复杂度是$O(n\alpha(n))$。
编程技术技巧
此时是并查集的模版题,其中的大部分代码可以直接复用。
不过,虽然并查集本身的操作复杂度很低,我们仍然可以对$Union$操作进行些许的优化。因为这里就题目而言,我们一定会在$Union$操作之前进行两次的$Find$操作,所以这里可以直接将上一步中得到的$x$和$y$的祖先节点,传入$Union$函数中,就不用在$Union$函数中反复的调用了。
Poj 1733 Parity game
问题描述
Now and then you play the following game with your friend. Your friend writes down a sequence consisting of zeroes and ones. You choose a continuous subsequence (for example the subsequence from the third to the fifth digit inclusively) and ask him, whether this subsequence contains even or odd number of ones. Your friend answers your question and you can ask him about another subsequence and so on. Your task is to guess the entire sequence of numbers.
You suspect some of your friend’s answers may not be correct and you want to convict him of falsehood. Thus you have decided to write a program to help you in this matter. The program will receive a series of your questions together with the answers you have received from your friend. The aim of this program is to find the first answer which is provably wrong, i.e. that there exists a sequence satisfying answers to all the previous questions, but no such sequence satisfies this answer.
Input
The first line of input contains one number, which is the length of the sequence of zeroes and ones. This length is less or equal to 1000000000. In the second line, there is one positive integer which is the number of questions asked and answers to them. The number of questions and answers is less or equal to 5000. The remaining lines specify questions and answers. Each line contains one question and the answer to this question: two integers (the position of the first and last digit in the chosen subsequence) and one word which is either ‘’even’’ or ‘’odd’’ (the answer, i.e. the parity of the number of ones in the chosen subsequence, where ‘’even’’ means an even number of ones and ‘’odd’’ means an odd number).
Output
There is only one line in output containing one integer X. Number X says that there exists a sequence of zeroes and ones satisfying first X parity conditions, but there exists none satisfying X+1 conditions. If there exists a sequence of zeroes and ones satisfying all the given conditions, then number X should be the number of all the questions asked.
算法设计
这道题目虽然是使用并查集完成,但是内部的关系不是很容易理清。因为输入的区间是包括了端点,所以很容易出现了区间重合的情况不好区分,于是可以将左端点减一以后,看作是一个左开右闭区间,这样书写起来关系就可以比较清晰。
稍有计算机常识的都可以知道,对于一段数据的奇偶性进行运算可以使用异或 (^)的方法。我们可以通过此运算,对于中间关系进行求解。
但是,这道题还有一点很重要的技巧,因为输入的区间过于庞大,所以如果直接使用给定的范围开辟空间,十分容易卡空间。所以需要进行一个$hash$化的处理。$hash$的方法很多,比较简单的是使用C++的$STL$里面的$map$,进行处理。因为$map$内部使用了红黑树,有良好的平衡性,所以开销不是很高,编程极容易实现。
程序代码
|
|
性能分析
对于每一步的关系处理来说,都是$O(1)$的操作,所以仍然为最后的$O(\alpha(n))$级别。不过在$hash$的过程中,每一步是$O(\lg n)$的级别。所以最后的时间复杂度是由$hash$主导,为$O(n\lg n)$。在Poj平台上为235MS。
编程技术技巧
这道题目主要有三个特别注意的地方:
- 使用左开右闭区间代替原来的题目描述,方便编程和自己的理解。
- 使用异或操作降低复杂度,如果采用和第一题一样的取模的方法,从计算机系统的角度考虑耗时要高。
- 使用$STL$里的$map$来进行$hash$化的操作,开销较小,并且编程容易实现。
Poj 2912 Rochambeau
问题描述
N children are playing Rochambeau (scissors-rock-cloth) game with you. One of them is the judge. The rest children are divided into three groups (it is possible that some group is empty). You don’t know who is the judge, or how the children are grouped. Then the children start playing Rochambeau game for M rounds. Each round two children are arbitrarily selected to play Rochambeau for one once, and you will be told the outcome while not knowing which gesture the children presented. It is known that the children in the same group would present the same gesture (hence, two children in the same group always get draw when playing) and different groups for different gestures. The judge would present gesture randomly each time, hence no one knows what gesture the judge would present. Can you guess who is the judge after after the game ends? If you can, after how many rounds can you find out the judge at the earliest?
Input
Input contains multiple test cases. Each test case starts with two integers N and M (1 ≤ N ≤ 500, 0 ≤ M ≤ 2,000) in one line, which are the number of children and the number of rounds. Following are M lines, each line contains two integers in [0, N) separated by one symbol. The two integers are the IDs of the two children selected to play Rochambeau for this round. The symbol may be “=”, “>” or “<”, referring to a draw, that first child wins and that second child wins respectively.
Output
There is only one line for each test case. If the judge can be found, print the ID of the judge, and the least number of rounds after which the judge can be uniquely determined. If the judge can not be found, or the outcomes of the M rounds of game are inconsistent, print the corresponding message.
算法设计
本题的思路和食物链基本一致,甚至解题主体都是差不多的。唯一的区别是引入了一个裁判,这个裁判不属于任何的集合,每次都可以说不同的话。所以为了找出谁是裁判,需要对于每个人进行一次假设,判断如果他是裁判,能不能没有冲突。所以这里需要循环$n$次。如果没有一个是满足的,则输出”Impossible”,如果有很多裁判都可以导致没有冲突,则输出”Can not determine”。
程序代码
|
|
性能分析
因为内部需要对裁判的可能性进行判断,所以进行$n$次的遍历。总的复杂度为$O(n^2\alpha(n))$。
编程技术技巧
思路和食物链基本一致,可以参考前面的编程技巧。