不相交集用来解决等价问题，特点是编程实现很简单但是分析复杂。

关系：对于每一对元素，或者为true或者为false，称在集合S上定义关系R。若aRb是true，那么a和b有关系

等价关系：是满足以下3个性质的关系R：

1.自反性，对所有，aRa

2.对称性，aRb当且仅当bRa

3.传递性，若aRb，bRc，那么aRc

一个例子：不是等价关系，满足自反性和传递性，但是不满足对称性

用来解决等价问题的数据结构：

1.使用二维数组，缺点是浪费大量空间，比如若定义~是等价关系，那么a~b，b~c，c~d就足够判断abcd4个元素是相互等价的，但是二维布尔数组来表示这个问题很不明显

2.使用等价类，一个元素的等价类是S的一个子集，包含所有和a有关系的元素，注意，每个元素只能出现在一个等价类中，否则按照传递性，两个等价类将合并。这样，为了验证a~b，只要验证a和b是否在一个等价类中。等价类的数据结构描述：初始输入是N个集合的类，每个集合中只有一个元素，集合之间不相交，允许使用两种运算：

Find：返回给定元素的集合的名字

Union：将a和b所在的两个等价类合并成一个新的等价类

称为不相交集的find/union运算，这是一个联机算法，执行过程中，集合通过union改变

方案：解决动态等价问题有两种方案，一种保证find常数时间，一种保证union常数时间，这两者不能同时做到。

代码如下：

#include <stdio.h>

#define NumSets   128

typedef int DisjSet[NumSets + 1];
typedef int SetType;
typedef int ElementType;

void Initialize(DisjSet S);
void SetUnion(DisjSet S, SetType Root1, SetType Root2);
SetType Find(ElementType X, DisjSet S);

/* 隐式的树，值为0表示自己是根，初始的时候，每个元素都是根 */
void Initialize(DisjSet S)
{
    int i;

    for (i = NumSets; i > 0; i--)
        S[i] = 0;
}

/* 合并，将Root2的根设置为Root1 */
void SetUnion(DisjSet S, SetType Root1, SetType Root2)
{
    S[Root2] = Root1;
}

/* 查找根，递归直到值为0，就找到了一个根，返回在数组中的位置 */
SetType Find(ElementType X, DisjSet S)
{
    if (S[X] <= 0)
        return X;
    else
        return Find(S[X], S);
}

两种灵巧求并的改进：

1.按大小求并

上面的代码中，union操作是无条件的，可以按大小求并，每次将小的合并到大的上，这样，深度最多是logN，因为每次合并都被放到至少是原来节点2倍的树中，一共可以合并logN次，也就是说find操作的时间是logN，M次find操作的时间是O(MlogN)，最坏情况就是二项队列中的二项树。改进方法是，原来数组中值为0表示是根，改成节点个数的负值，初始时所有节点都是-1，后续union的时候，根所在节点的负值增加

2.按高度求并

和按大小求并类似，也保证深度最多O(logN)，按高度求并代码如下

void SetUnion(DisjSet S, SetType Root1, SetType Root2)
{
    /* 若Root2更深，那么将Root1合并到Root2上 */
    if (S[Root2] < S[Root1])
        S[Root1] = S[Root2];
    else
    {
        /* 若高度相等，那么增加高度 */
        if (S[Root1] == S[Root2])
            S[Root1]--;
        S[Root2] = Root1;
    }
}


路径压缩：对于连续M次操作，平均时间是O(M)，但是最坏的O(MlogN)时间会发生，比如union之后形成了一个二项树。对union无法改进，因为无论按照何种方法执行union，都会造出来一个相同的最坏情形的树，也就是二项树，改进find如下：每次find(X)之后，从X到根的每个节点都让它的父节点变成根，只要对代码进行一点改进就可以实现，如下：

SetType Find(ElementType X, DisjSet S)
{
    if (S[X] <= 0)
        return X;
    else
        return S[X] = Find(S[X], S);
}


路径压缩和按照大小求并完成兼容，但是和按高度求并不兼容，因为会修改树的高度，但是可以使用秩，作为估计的高度

按秩求并和路径压缩的最坏情形：使用这两种方法，算法在最坏情形下几乎是线性的，精确时间是，其中，是Ackermann函数的逆，Ackermann函数如下定义：







由此定义，在实际应用中，。单变量反Ackermann函数写成，是N的直到的取对数的次数，，，增长的比还慢，不过不是常数，导致时间不是线性的

结论：使用路径压缩和按秩求并，任意顺序的次Union/Find操作花费的时间是

分析：Union和Find操作可以以任何顺序出现，Union按秩进行，Find使用路径压缩

引理1：执行一系列Union指令时，一个秩为r的节点必然至少有个后裔，包括自己

证明：数学归纳法

引理2：秩为r的节点的个数最多是

证明：秩为r的节点至少有个子节点，一共N个节点，所以得到这个个数

引理3：在Union/Find算法的任一时刻，从树叶到根的路径上的节点的秩单调增加

证明：显然

记账法则：对于从代表i的定点到根的路径上的所有顶点v，在两个账户之一存入一个分币：

法则1.若v是根，或者v的父亲是根，或者v的父亲和v在不同的秩组中，那么将一个美分存入公共储金

法则2.否则，将一个canada分币存入该顶点中

引理4：对任意的find(v)，无论存入总储金还是存入顶点，所存分币总数恰好等于从v到根的路径上的节点数

证明：显然

引理5：经过整个算法，在法则1下美分存入的总的数量是

证明：对于任意find，有根和根的儿子，有2个，由于一个路径上节点的秩单调递增，一共G(N)个秩组，因此一共还可以放G(N)个，M次find总的数量就是

引理6：秩组g > 0中顶点的个数至多为

证明：由引理2，至多存在个秩为r的节点，对秩组g中的秩求和，得到



          

          

          

          

          

引理7：存入秩组g的所有顶点的canada分币的最大的个数至多是

证明：秩组g中有个节点，应用引理6得到结果

引理8：在法则2下存入分币最多是个canada分币

证明：显然

综上，法则1和法则2总的分币数是

定理：M次Union和Find的运行时间是

证明：F是和递归定义的函数，，将F和G定义插入到引理8中，得到结论

    总是搞不清楚指针、引用、数组、数组指针、指针数组等等一堆东西之间的关系和用法，学习C++ Primer之后，稍作总结，希望对需要的人有帮助，以下的文字基本上都是来自C++ Primer3的书中<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

1、数组参数：
int* 、int[] 、 int[ 10 ]作为函数的参数是等价的
在被调函数内对参数数组的改变将被应用到数组实参上而不是本地拷贝上。
数组长度不是参数类型的一部分函数不知道传递给它的数组的实际长度编译器也不知道当编译器对实参类型进行参数类型检查时并不检查数组的长度

2、传递数组长度的方法
①是提供一个含有数组长度的额外参数
void putValues( int[], int size );
②是将参数声明为数组的引用
void putValues( int (&arr)[10] );
③是使用抽象容器类型
void putValues( vector<int> vec )
另：
参数也可以是多维数组这样的参数必须指明第一维以外的所有维的长度例如：
void putValues( int matrix[][1a], int rowSize );多维数组的参数类型检查只检验多维数组实参中除了第一维之外的所有维的长度与参数的是否相同
int *matrix[ 10 ];将matrix 声明成一个含有10 个指向int 的指针的数组
int (*matrix)[10];把matrix 声明成一个二维数组每行由10 个列元素构成matrix 
int (&arr)[10];将参数声明为数组的引用当参数是一个数组类型的引用时数组长度成为参数和实参类型的一部分编译器检查数组实参的长度与在函数参数类型中指定的长度是否匹配

 
３、指针和引用作为参数的优缺点，以及何决定使用：
两种参数都允许函数修改实参指向的对象，两种类型的参数都允许有效地向函数传递大型类对象
指针可能指向一个对象或没有任何对象所以函数在确定指针实际指向一个有效的对象之前不能安全地解引用一个指针；对于引用参数函数不需要保证它指向一个对象引用必须指向一个对象甚至在我们不希望这样时也是如此。
如果一个参数可能在函数中指向不同的对象或者这个参数可能不指向任何对象则必须使用指针参数；引用参数的一个重要用法是它允许我们在有效地实现重载操作符的同时还能保证用法的直观性