并查集最擅长做的事情——将两个元素合并到同一集合、判断两个元素是否在同一集合中。 并查集用到了树的父结点表示法。在并查集中,每个元素都保存自己的父亲结点的编号,如果自己就是根 结点,那么父亲结点就是自己。这样就可以用树形结构把在同一集合的点连接到一起了。 (1) 并查集的实现 struct node { int parent; // 表示父亲结点。当编号i==parent时为根结点。 int count; // 当且仅当为根结点时有意义:表示自己及子树元素的个数 int value; // 结点的值 } set[N]; int Find(int x) // 查找算法的递归版本(建议不用这个) { return (set[x].parent==x) ? x : (set[x].parent = Find(set[x].parent)); } int Find(int x) // 查找算法的非递归版本 { int y=x; while (set[y].parent != y) // 寻找父亲结点 y = set[y].parent; while (x!=y) // 路径压缩,即把途中经过的结点的父亲全部改成y。 { int temp = set[x].parent; set[x].parent = y; x = temp; } return y; } void Union(int x, int y) // 小写的union是关键字。 { x=Find(x); y=Find(y); // 寻找各自的根结点 if (x==y) return; // 如果不在同一个集合,合并 if (set[x].count > set[y].count) // 启发式合并,使树的高度尽量小一些 { set[y].parent = x; set[x].count += set[y].count; } else { set[x].parent = y; set[y].count += set[x].count; } } void Init(int cnt) // 初始化并查集,cnt是元素个数 { for (int i=1; i<=cnt; i++) { set.parent=i; set.count=1; set.value=0; } } void compress(int cnt) // 合并结束,再进行一次路径压缩 { for (int i=1; i<=cnt; i++) Find(i); } |
说明: Ÿ 使用之前调用Init()! Ÿ Union(x,y):把 x 和 y 进行启发式合并,即让节点数比较多的那棵树作为“树根”,以降低层次。 Ÿ Find(x):寻找 x 所在树的根结点。Find的时候,顺便进行了路径压缩。 上面的Find有两个版本,一个是递归的,另一个是非递归的。 Ÿ 判断 x 和 y 是否在同一集合:if (Find(x)==Find(y)) …… Ÿ 在所有的合并操作结束后,应该执行compress()。 Ÿ 并查集的效率很高,执行 m 次查找的时间约为O(5m)。
|