首页

# 并查集

解决问题：

  • 快速知道 x 在哪个集合。
  • 快速判断 x ， y 是否在同一个集合，其实就是运用特点一。

为了便于体现，使用数组下标表示元素 x ，数组元素表示集合 —— i 表示元素， arr[i] 表示集合。

初始化，我们让所有元素都属于自己那个集合：

// 具体方法名啥的省略
for(int i = 0; i < n ; i++) {
    arr[i] = i;
}

# 最慢的合并

并查集的思想是，当我们想合并两个元素：将 i 与 j 合并，就要将 i 所在集合的所有元素合并到 j 所在集合。

// 合并：默认 x，y 没有越界
public void union(int x, int y) {
    for(int i = 0 ; i < n ; i ++) {
		 if(arr[i] == arr[x]) arr[i] = arr[y];
	}
}
// 查找：查找 x 所在集合
public int find(int x) {
    return arr[x];
}
总结：
  • 合并很慢，每次合并操作都是 O(n) 。
  • 查询很快， O(1) 。
# 快合并慢查询
这里的慢查询，最坏的情况还是 O(n) 。
我们不妨设定每个元素所在的集合有一个大哥，每个元素的指向路径的终点都是这个大哥。
举个例子：
  • 每个元素一开始都指向自己，表示自己所在的集合。
  • x 合并到 y ，那么 arr[x] = y ，用节点表示就是 (x) -> (y) ，然后将 y 合并到 z 。
  • 这个合并过程不会改变 x 的指向，也就是 arr[x] 还是 y ，那么整个指向就变成了 (x)->(y)->(z) 。
  • 每个节点的指向路径的终点都是 z ， z 就是这个集合的大哥，另类地说，其他元素都在 z 集合中。
// 查询
public int find(int x) {
	// 就像链表一样不断向下查询。
    while(x != arr[x]) {
        x = arr[x];
    }
}
// 合并
public void union(int x, int y) {
    int endFisrt = find(x);
    int endSecond = find(y);
    
    // 不论 endFirst 是否等于 endSecond 同一个集合，都可以进行下面的操作
    arr[endFirst] = arr[endSecond];
}
详细合并如图：
缺点：合并可能会导致树退化为单链表，导致 find() 时间复杂度上升。
# 基于重量合并
其实合并 x ， y 并不是非要 x 并入 y ，也可以是 y 并入 x 。基于重量合并，就是集合元素少的合并到集合元素多的里面。
我们只需要额外开一个数组记录带头大哥有多少个小弟即可：
// 初始化 weight [i] = 1;
// 合并
public void union(int x, int y) {
    int endFirst = find(x);
    int endSecond = find(y);
    
    if(endFirst == endSecond) return;
    else if(weight[endFirst] > weight[endSecond]) {
        arr[endSecond] = arr[endFirst];
        weight[endFirst] += weight[endSecond];
    } else { // 等于的时候随便合并
        arr[endFrist] = arr[endSecond];
        weight[endSecond] += weight[endFirst];
    }
}
# 空间压缩优化
在查询的时候可以压缩空间，使得之后查询用时减少，这种方法只能用于重量合并。
public int find(int x) {
	while(x != arr[x]) {
        // 让 x 指向父亲的父亲，这就使得整个链表逐渐变短
        arr[x] = arr[arr[x]];
        x = arr[x];
    }
}
# 基于高度合并
根据高度，很简单，矮的合并到高的，直接看图不多说：
同理，需要额外空间记录老大哥高度：
// 初始化 height [i] = 1;
public void union(int x, int y) {
    int endFirst = find(x);
    int endSecond = find(y);
    
    if(endFirst == endSecond) return;
    else if (height[endFirst] < height[endSecond]) {
        arr[endFirst] = arr[endSecond];
    } else if (height[endFirst] > height[endSecond]) {
        arr[endSecond] = arr[endFirst];
    } else {
        // 随便哪个合并到哪个
        arr[endSecond] = arr[endFirst];
    	height[endSecond]++;
    }
}
# 参考
https://www.cnblogs.com/noking/p/8018609.html