The Suspects以及并查集总结

The Suspects以及并查集总结

• 题目
• 基本并查集
• Size优化并查集
• Rank优化并查集
• 路径压缩优化一(最好)
• 路径压缩优化二(递归)

题目链接

http://poj.org/problem?id=1611

题意

就是告诉你0号同学被感染了，他还参加了一些社团，给出一些社团以及里面的人，问总共多少人感染。输入给出n表示人数(标号为0~n-1)，m表示社团数目，接下来m行每行第一个数k ，表示该社团有k人，然后是k个人的编号。要你输出有多少个人感染了病毒。

解析

题目本身并不难:

• 把每个社团加入到各自的集合中，然后不断的合并相同的集合，最后看哪些和0号同学在同一个集合中，使用一个变量记录和0号同学在同一个集合中的人数即可；
• 这里主要是总结并查集几种优化的方式；

基本并查集

基本并查集，记录一个每个结点p的父亲结点是parent[p]，然后是一个不断从孩子找父亲的过程:

• find()操作， while(p != parent[p])p = parent[p]，一直往上找根的过程；
• union()操作，就是找到两个结点的根节点，然后将其中一个结点的根节点挂到另一个结点的根节点即可；

例如: union()操作合并6和3所在的集合:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70	``` import java.io.BufferedInputStream; import java.util.Scanner; public class Main { static class UnionSet { private int[] parent; public UnionSet(int size) { parent = new int[size]; /** 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合 */ for (int i = 0; i < size; i++) parent[i] = i; } public int size() { return parent.length; } // 查找过程, 查找元素p所对应的集合编号 private int find(int p) { if (p < 0

---

Size优化并查集

• 在union()操作中，有一种情况会使得我们的集合变得深度很深，这对查询来说是会降低效率的；
• 例如下面的union，合并3和9所在的集合，如果我们将3的根8挂在9下面，会使得高度变成4：(不好的）；

于是，我们的解决办法是:

• 每一个集合记录一个size，在union()操作的时候，我们将size小的挂到size大的下面，这样会使得深度稍微小一点；
• 操作完之后记得维护被挂的那个集合的size()；

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49	``` static class UnionSet{ private int[] parent; private int[] sz; // sz[i]表示以i为根的集合中元素个数 public UnionSet(int size) { parent = new int[size]; sz = new int[size]; /** 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合 */ for( int i = 0 ; i < size ; i ++ ) { parent[i] = i; sz[i] = 1; } } public int size(){ return parent.length; } private int find(int p){ if(p < 0

---

Rank优化并查集

• 基于rank的优化，其中rank[i]表示的是根节点为i的树的高度；

发现问题:

• 虽然上面的size优化已经很不错，但是如果出现下面的情况，例如合并0和3所在的集合，如下，这样会使得高度变成4，而如果反着合并就只需要变成3；
• 于是我们需要记录的不是size，而是记录一个高度rank即可；

下面是改造的做法，我们将高度小的挂在高度大的下面，这样使得深度更低；

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51	``` static class UnionSet{ private int[] parent; private int[] rank; // rank[i]表示以i为根的集合所表示的树的层数 public UnionSet(int size) { parent = new int[size]; rank = new int[size]; for( int i = 0 ; i < size ; i ++ ) { parent[i] = i; rank[i] = 1; } } public int size(){ return parent.length; } private int find(int p){ if(p < 0

---

路径压缩优化一(最好)

并查集另一个优化就是路径压缩:

• 例如下面的三个集合是等价的，但是查询的效率确实逐渐的增加的，第一个查询效率最低，第三个查询效率最高；
• 我们需要做的就是在find()的时候，沿途将查找的孩子结点改变他们的父亲parent达到路径压缩的目的；

首先来看改造成第二个版本: (使用非递归 )

• 这个优化就是对于沿途的结点，我们从底到上，依次更改他们的父亲结点为他们的父亲结点的父亲结点(parent[p] = parent[parent[p]] )；
• 例如我们查询find(4)，第一步，我们先将parent[4] = 2，（2就是4的父亲(3)的父亲）；

• 继续往上，把2的父亲结点改为2的父亲结点的父亲结点，也就是0结点，此时我们的树结构变成了下面的样子；

于是我们就完成了从第一种情况到第二种情况的优化:

• 代码如下： 在代码中的更改只有上一个版本中find()函数中增加了一行代码: parent[p] = parent[parent[p]]；

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54	``` static class UnionSet{ private int[] parent; /** * 在后续的代码中, 我们并不会维护rank的语意, 也就是rank的值在路径压缩的过程中, 有可能不在是树的层数值 * 这也是我们的rank不叫height或者depth的原因, 他只是作为比较的一个标准 */ private int[] rank; public UnionSet(int size) { parent = new int[size]; rank = new int[size]; for( int i = 0 ; i < size ; i ++ ) { parent[i] = i; rank[i] = 1; } } public int size(){ return parent.length; } private int find(int p){ if(p < 0

---

路径压缩优化二(递归)

继续完成从第一种情况到第三种情况的优化，其实核心代码只有几行:

1 2 3 4 5	private int find(int p){ if(p != parent[p]) parent[p] = find(parent[p]); return parent[p]; }

• 我们宏观的就是将parent[p]执行了最终的那个根节点，并返回了；

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48	``` static class UnionSet{ private int[] parent; private int[] rank; public UnionSet(int size) { parent = new int[size]; rank = new int[size]; for( int i = 0 ; i < size ; i ++ ) { parent[i] = i; rank[i] = 1; } } public int size(){ return parent.length; } private int find(int p){ if(p < 0

---

POJ上测试效率对比，从下到上，从版本一到版本五的时间: