乱八七糟的代码

Steps to developing a usable algorithm.
• Define the problem.
• Find an algorithm to solve it.
• Fast enough?
• If not, figure out why.
• Find a way to address the problem.
• Iterate until satisfied.

主要内容 FIND-UNION ALGORITHM

就是利用并查集来考察连通性的算法 。条件N个节点，M对节点，输入每一对节点时候，如果已经连通，则忽略，否则输出接点并更新

主要介绍三种算法：第一种，QUCK-FIND 利用数组记录每一个联通子图，同一个联通子图的节点数组变量是相同的。因此每读入一对就需要遍历N个数组变量考察是否需要更新，最坏时间MN，实际上每个子图为高度为2的树;第二种，QUICK-UNION 联通子图需要union时 仅仅需要将两个root union 因此每个联通子图高度变高，所有find root 会消耗一定时间，当然无需遍历N了 ，最坏时间，也就是每次均需要从叶子节点去回溯求根（这里书中举得例子好像有问题）也是MN；第三种也就是 QUICK WEIGHT UNION 这种方法在两个子树合并的时候，不是简单的指定合并策略，而是经过判断的，把size小（相应高度也小）的合并到size大的里面；实际上很容易理解就是尽量减少树的高度来追求quick-find的效率；

进而作者写道路径压缩，也是这种思想。或者实现为全部压缩，也就是说在进行union操作的时候，所有check的节点都直接链接到union后的新root下面，或者half union （容易实现且性能好）每次check时候，如果没有停止loop简单的令 id[i]=id[id[i]];即可达到减少到根距离的效果。

half union 的主要代码：

int i,j;
for(i=p;id[i]!=i;i=id[i]) id[i]=id[id[i]];
for(j=p;id[j]!=j;j=id[j]) id[j]=id[id[j]];
if(i==j)continue;
if(size[i]>size[j]) id[j]=i,size[i]+=size[j];
else        id[i]=j,size[j]+=size[i];

第一次用windows live writer 试试效果哦~~