并查集（Disjoint-set Forests）

    我们可能会遇到一些问题（including handling EQUIVALENCE and COMMON statements in FORTRAN , finding minimum spanning trees, computing dominators in directed graphs, checking flow graphs for reducibility, calculating depths in trees, computing least common ancestors in trees, and solving an offline minimum problem，以上摘自《Efficiency of a Good But Not Linear Set Union Algorithm》, ROBERT ENDRE TARJAN），与将n个不同的元素合并为一些不相交集合（Disjoint Sets）有关。这种问题往往包含两种操作， 一种是所谓的询问操作（Find），即寻找某一个元素当前在哪一个集合中；另一种则是合并操作（Union），把某两个集合合并为一个集合（ 开始的时候n个元素即为n个集合）。我们需要有效的数据结构和算法实现这两种操作。 
　

    我们很难寻找到一个集合的简单的表示方法——集合的最小表示时间复杂度过高，而且在这个问题中并不实用。 事实上，由于这里的集合都是不相交的，因此我们可以使用集合中的任意一个元素作为这个集合的代表（Representative）来唯一地确定这个集合。 这样不仅简化了集合的表示，而且我们之后可以看到，它将起到非常重要的作用。

    以下是使用了代表表示法之后，几种操作的简单实现方法：

    一个最自然的想法是使用数组来模拟合并的过程。 定义一个二维数组a[i][j]，i表示第几个集合，j表示这个集合中的第几个数。我们可以预见到这样的数据结构将导致暴力的合并操作（O（n） 的时间复杂度）和询问操作（同样是O(n)的时间复杂度，虽然通过加入一个pos[i]数组可以降低为O(1)）。 即使通过一些优化，我们可以把常数降低，但是面对n^2的空间复杂度，我们不得不直接放弃这个想法。

    而紧接着的想法就是使用链表了。 其实几乎所有用数组实现的算法都可以使用链表实现，虽然时间效率上会有常数上的差异。使用链表的话我们需要对每一个元素定义三个值：代表的位置、ID、同集合中的下一个元素位置。这三个值都是必要的， 与数组实现的不同之处就是我们只使用了O（n）的空间。但是合并操作在极端境况下仍需要平均O（n）的复杂度：

    合并操作的时候，假设面对两个集合S1，S2。 我们把S2的所有元素都并入S1中并改变S2的所有元素的“代表的位置”的值，那么我们这次操作的时间复杂度是O（|S2|）。面对开始时候的S1,S2,S3,…,Sn， 假设我们需要进行如下的合并操作：

    Union(S2,S1);

    Union(S3,S2);

    Union(S4,S3);

    …

    Union(Sn,Sn-1)

    那么我们需要O(n^2)的时间来完成这些操作。 
　

    下面我们加入一个简单的启发策略——加权式启发策略（Weighted-Union Heuristic）：当每次合并集合的时候，我们总是把元素个数少的集合合并到元素个数多的集合中去。虽然这个启发策略看起来很弱， 但是可以证明这个策略使Union的平摊时间复杂度降低为O(lgn)。 
 
　

（以上内容参考《算法导论第二版》（《INTRODUCTION TO ALGORITHMS SECOND EDITION》）第21章：用于不相交集合的数据结构（Data Structures for Disjoint Sets）） 
 
　

    在推出并查集的想法之前， 我们应该想想我们是如何想到可能有这个想法的存在的（或者说Tarjan是如何想到这个想法的存在的），即，我们之间的朴素想法是否存在冗余？

    既然是朴素的算法，那自然是有冗余存在的。 有一个很不错的想法起源于懒人逻辑：如果有一件事情早做晚做都一样，那么我宁愿晚做。由于询问操作的时间复杂度是O（1）的， 所以算法的瓶颈位于合并操作中；而合并操作的时间复杂度由两部分组成：O（生成新的集合）+O（修改集合代表）。

    显然O（生成新的集合）的时间复杂度是O（1）的， 所以真正的瓶颈位于O（修改集合代表）。

    那么， 修改集合代表这个操作会对之后的什么操作有影响呢？

    由于我们的目的是应付所有的询问操作， 即x元素现在位于哪一个集合中。所以，修改x元素的集合代表这个操作，从合并x元素所在集合， 到对x进行询问操作这段时间内任何时间都可以做而对算法的正确性没有影响。应用懒人逻辑，我们完全可以先把这个操作记录下来， 在对x询问进行询问操作的时候再处理。

    于是，我们就得到了一个森林（Disjoint-set Forest）的结构，森林里的每一棵树都代表了一个集合。树的根结点表示这个集合的代表，树的非根结点则代表了集合中的其余元素。 每一个结点都有一个指针指向了自己所在集合的代表，但是这个指针未必是实时更新的——也就是说， 这个指针指向的元素A可能在某一次合并操作之后不再是代表了。但是由于元素A的指针指向在那次合并操作之后的新的代表B， 而B也会有指针指向代表C……直到某一个元素的指针指向了自己，我们就会知道，这个元素是真正的根结点， 也就是目前的集合的代表。虽然看起来这样顺藤摸瓜很是麻烦，但是这个方法的操作数是小于等于之前的合并操作使用的操作数的（ 有些没有被询问到的元素的指针就永远不会被更新）。

    懒人的方法自然要优秀一点，但也并不优秀到哪里去。 因为目前的方法并没有真正降低算法的时间复杂度。但是我们将看到，在这个新的数据结构中，通过加入两个优秀的启发式策略，我们将获得目前已知的、 渐近意义上最快的不相交集合的数据结构。 
　

    在提出这两个启发式策略之前，我们不妨自己考虑一下， 有什么样的启发式策略可以加入这个森林的结构呢？作为与数组、链表不同的树结构，它到底有什么方面的优势呢？ 虽然看起来独立地创造出这些策略并不是我辈能力所及，但其实并非如此。事实上，远在Tarjan正式地证明并查集的时间复杂度（1975） 之前的六十年代，很多程序员都会在自己的程序中加入这些启发式策略，因为这些策略帮助他们的程序更加快速地运行， 只是大家都不知道这些策略到底多么有效，它们在最坏情况下会有什么样子的表现。因此如果仅仅是提出策略而不证明，我们完全是有这个能力的。

    这里，我们再度搬出懒人逻辑。 其实懒人逻辑的本质是消除冗余，而正如某人说过的，提高效率的关键就是消除冗余。在不断地消除冗余的过程中，我们将一步步地提高程序效率。

    首先，受到之前的加权式启发策略的影响， 我们可以考虑到，在这个森林结构中也可以加入一个类似的启发策略。我们知道给树加权常用两种方法，一种是以树的高度为标准的； 一种是以树的结点个数为标准的。我个人是倾向于以树的结点个数为标准的加权策略，但是Tarjan给出的启发式策略是以树的高度为标准的， 叫做按秩合并（Union by Rank）。（这里我一直有一个疑问，因为我觉得以树的结点个数为标准效果不会比以树的高度为标准差。 我查阅的资料中没有什么明确的答案，貌似是因为以高度为标准的时候，算法的时间复杂度更加容易计算。就我个人多年的实践经验而言， 我一直是使用按照结点个数为标准的启发函数的，而执行效率不比标准算法差，甚至在某些测试中表现更加优秀。）

    具体的按秩合并的操作是这样的： 刚开始的时候每一棵树的秩都是0。当执行合并操作的时候，如果即将合并的两棵树的秩是相等的，任选一颗树的根作为新的根合并，并且把这棵树的秩加1； 否则选择秩更大的树的根作为新的根，秩不变。秩的定义是，这棵树的根结点到叶结点的路径的最大长度的上界。（ 也就是树的深度的上界，但由于有了路径压缩的启发式策略，未必是上确界）

    既然这个启发策略和之前的加权式启发策略类似， 我们自然不能指望它的效率能够有大幅上涨。事实上，它的均摊时间复杂度仍然是O(lgn)的。我们需要更强的启发式策略。

    考虑询问操作时，针对某一个结点的“顺藤摸瓜”找代表时的具体操作。我们必须清醒地意识到， 所有的时间复杂度来源于这一顺藤摸瓜的过程，而要提高算法效率的关键也就在这里。

    有一个非常简单的想法就是，每次顺藤摸瓜的过程中， 摸到的每一个结点，都是在同一个集合中的；而这些结点的代表自然也就是最后找到的根结点。我们可以把这些结点的指针全部都指向该根结点，这样， 以后进行询问操作顺藤摸瓜的时候，一旦摸到了这些结点中的某一个，我们就不需要继续摸这么长的藤，可以直接跳到根结点（ 当然这个时侯这个根结点可能已经变成非根结点了）。

    这两个启发式策略就是这么简单。但是我们可以证明， 使用了这两个启发式策略之后，最坏情况下的时间复杂度为O(mа(n))，其中а(n)是一个增长极端缓慢的函数， 在任何我们可以想象到的情况中，а(n)都不会超过4。 因此我们认为这个算法的时间复杂度几乎是线性的。 
　

1.Ackermann函数和它的反函数

2.秩的性质

    （请注意将这里的秩的性质，和在另一种启发式策略， 即以结点个数为标准的策略中，树的结点个数的性质进行比较，它们共有这些性质）

应用题解：食物链

动物王国中有三类动物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），输出假话的总数。

输入文件（eat.in）

第一行是两个整数N和K，以一个空格分隔。

以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。

  若D=1，则表示X和Y是同类。

  若D=2，则表示X吃Y。

输出文件（eat.out）

只有一个整数，表示假话的数目。

输入样例

输出样例

3