第一部分：问题示例：连通性（connectivity) 假如已知一个整数对（pair)序列，其中每个整数代表某种类型的一个对象，而且将p-q对解释成“p与q连通”。 假定关系“与.......”是可传递的：如果p与q连通，同时q与r连通，则p与r连通. 我们的目的是编写一段程序，从集合(set）中过滤额外连接对；当程序输入一个对p-q，仅当程序此时已经看到的对不能通过可传递性证明p与q连通时，它才输出该对。如果前面的对表明p与q连通，则程序应该忽略p-q，并继续输入下一个对。如：3-4 3-44-9 4-98-0 8-02-3 2-35-6 5-62-9 2-3-4-95-9 5-97-3 7-34-8 4-85-6 5-60-2 0-8-4-3-26-1 6-1 注释已知一个代表对象间连通性的整数对序列（一楼左边一列）连通性算法的任务是输出那些提供了新连通的对（中间一列）如：对2-9不在输出列中，因为前面的连通暗示存在2-3-4-9连通（右边的为推论佐证）好了，我先吃饭去了 

由于算法非常多，内容也非常广泛所以我只能列举几个希望大家谅解今天讲的是：连通性问题的快速查找解决方案：#include
#define N 10000main(){ int i,p,q,t,id[N]; for(i=0;i

连通性问题的快速并集解决方案： 如果我们用下面代码替换上面程序中的while循环体，得到的结果是同样的，但并集运算计算量少，查找运算计算量大。代码中的for循环以及后面的if语句定义了p和q连通的id数组的必要且充分条件。 赋值语句id[i]=j实现并集运算,代码如下： for(i=p;i!=id[i];i=id[i]); for(j=q;j!=id[j];j=id[j]); if(i==j) continue; id[i]=j; printf("%d %d\n",p,q);

快速并集的加权版本 这个程序是快速并集算法（上一个）的修改版本，它使用一个额外的数组sz完成维护的目的，为每个对象用id[i]==i来表示，即在关联树中节点的数量。因此，并集运算可以连接两棵指定树中的较小者与较大者，以此阻止树中长路径的增长。#include
#define N 10000main(){int i,j,p,q,id[N],sz[N]; for(i=0;i

对分路径压缩： 如果我们用如下代码替换上一个程序中的for循环，就可以对分我们所遍历的路径长度。这种变化的最终结果是，经过一个长运算序列后，树变得几乎完全扁平。for(i=p;i!=id[i];i=id[i]) id[i]=id[id[i]];for(j=q;j!=id[j];j=id[j]) id[j]=id[id[j]];

不错

多发几个过来!!!

也，我也看了这本书，第一章就讲这个并集查找，看的人心旷神怡的

请教一下谁知道在哪有买

顶一下！！！！

也正在看此书~~~

不错

23331

对于第一个算法，当我把２９放在最前边的话，输出的结果中怎么２９也输出了呀，

C算法容易理解不?

算法是灵魂！！！！！！！！！！！！！！！

sfadf

楼主给我讲讲 基于连通性状态压缩的动态规划