并查集的一些应用加递归和非模板

1、并查集：(union-find sets)是一种简单的用途广泛的集合. 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多，如其求无向图的连通分量个数、最小公共祖先、带限制的作业排序，还有 最完美的应用：实现 Kruskar 算法求最小生成树。其实，这一部分算法导论讲的很精炼。一般采取树形结构来并查集，在合并操作时可以利用树的节点数(规则)或者利用一个r数组来集合的深度下界-启发式函数，在查找操作时进行路径压缩使后续的查找操作加速。这 样优化实现的并查集，空间复杂度为 O(N)，建立一个集合的时间复杂度为 O(1)，N 次合并 M 查找的时间复杂度为 O(M Alp

2、ha(N)，这里 Alpha 是 Ackerman 函数的某个反函数，在很大的范围内这个函数的值可以看成是不大于 4 的，所以并查集的操作可以看作是线性的。它支持以下三种操作:Union (Root1, Root2) /合并操作；把子集合 Root2 和子集合 Root1 合并.要求：Root1 和 Root2 互不相交,否则不执行操作.Find (x) /搜索操作；搜索元素 x 所在的集合,并返回该集合的名字-根节点.UFSets (s) /构造函数。将并查集中 s 个元素初始化为s 个只有一个单元素的子集合.对于并查集来说，每个集合用一棵树表示。集合中每个元素的元素名分别存放在树的结点中，

3、此外，树的每一个结点还有一个指向其双亲结点的指针。为简化，忽略实际的集合名，仅用表示集合的树的根来标识集合。以下给出两种实现:/Abstract: UFSet/Author:Lifeng Wang （Fandywang）/ MOne 与 M2 路径压缩方式不同,合并标准不同constMAXSIZE = 500010;MAXSIZE; / 节点高度的上界rparentMAXSIZE; / 根节点FindSet(x)/ 查找+递归的路径压缩if( x != parentx ) parentx = FindSet(parentx); return parentx;void Union(root1,r

4、oot2)x = FindSet(root1), y = FindSet(root2);if( x = y ) return ;if( rx relseparentx = y;y ) parenty = x;if( rx = ry ) +ry;void Initi(void)memset(r, 0, s izeof();for(i =0; i 0 )p = prep; while( x != p )temp = prex; prex = p; x = temp;return x;void Union(r1,r2)a = Find(r1);if( a = b ) return ;/规则合并b =

5、 Find(r2);if( prea preb )prea += preb; preb = a;else preb += prea; prea = b;void Initi(void)for(i =0; i N; +i ) prei = -1;并查集的一些题目和相关解题:POJ 1611 Thes最基础的并查集POJ 2524 Ubiquitous Religions 最基本的并查集POJ 1182 食物链并查集的拓展注意: 只有一组数据;要充分利用题意所给条件:有三类动物 A,B,C，这三类动物的食物链了有趣的环形。A 吃 B， B 吃 C，C 吃 A。也就是说:只有三个 groupPOJ

6、2492 A Bugs Life 并查集的拓展法一:深度优先遍历每次遍历下该点是男还是女，只有:男-女，女-男满足，否则，找到，结束程序。法二:二分图匹配法三:并查集的拓展:和 1182 很像，只不过这里就有两组，而 1182 是三组,1611POJ 1861 Network = zju_1542并查集+自定义排序+贪心求最小生成树不唯一，不过在 ZOJ 上用 QSORT()和 SORT()都能过，在 POJ 上只有 SORT()才能过.POJ 1703 Find them, Catch them 并查集的拓展这个和 POJ 2492 A Bugs Life 很像，就是把代码稍微修改了一下就

7、AC 了！注意：And of course,east one of them belongs to Gang Dragon, and the same fang Snake. 就是说只有两个组。POJ 2236 Wireleetwork并查集的应用需要注意的地方：1、并查集；2、N 的范围，可以等于 1001；3、从 N+1 行开始，第一个输入的可以是字符串。POJ 1988 Cube Stacking并查集很好的应用1、与=NOI2002 Galaxy 一样；2、增加了一个数组 behindx,战舰 x 在列中的相对位置；3、详细解题见。JOJ 1905 Freckles= POJ 2560 最小生成树法一：Prim 算法；法二：并查集实现 Kruskar 算法求最小生成树JOJ 1966 Super M