【LeetCode】十六、并查集

文章目录

1、并查集Union Find
2、并查集find的优化：路径压缩 Quick find
3、并查集union的优化：权重标记
4、leetcode200：岛屿数量
- 解法一：DFS

1、并查集Union Find

并查集，一种树形的数据结构，处理不相交的两个集合的合并与查询问题。

【参考：📕经典解释】

引用上面文章的经典解释并查集：

一个集合就像一个江湖门派，他们有一个教主（代表元），集合中每个元素只需要记住自己的上级，而不是教主
find即查询某个元素的代表元（教主）
union即把两个门派（集合），合并成一个，认一个教主

在这里插入图片描述

例子：

在这里插入图片描述

查find(x)

有个数组array，长度为10，若array[1] = 6，说明1号元素的上级是6号元素。array[6] = 6，说明6号元素的上级是6号元素，即6号是教主。并查集的查：find(x)，即找x元素的教主

public int find(int x ) {
	// 如果x位置的值，等于x，说明x就是教主
	if (x == array[x]) {
		return array[x];
	}
	// 如果不是，查x位置的值的上级
	return find(array[x]);
}

也可不用递归：

public int find(int x ) {
	while(x != array[x]) {
		// 查x位置的元素自己的上级
		x = array[x];
	}
	return x;
}

并union(x,y)

两个集合合并，或者说两个门派合并，看似改动很大，其实只要让一个门派的教主给另一个门派的教主当上级即可。因为只关注两个集合的连通性。

// 传入两个门派的元素
public void union(int x, int y) {
	//查教主
	int rootX = find(x);
	int rootY = find(y);
	if (rootX != rootY) {
		// 让Y门派的教主当X门派教主的上级
		array[rootX] = rootY;
	}
}

如下树形，

在这里插入图片描述

对应的数组：数组索引代表元素，数组的值，代表这个位置的元素的上级

在这里插入图片描述

合并后，比如让第一个集合的教主做合并后新集合的教主：5号的上级不再是自己，变成了1

在这里插入图片描述

2、并查集find的优化：路径压缩 Quick find

用开头引用文章的形象例子，现在要做的就是，防止树形结构过于深，导致查询效率变低，将结果压缩成，只要查一次，就能知道教主是谁：

在这里插入图片描述

总之一句话，防止树太高，期待右边，而不是左边

在这里插入图片描述

想实现这个效果，可以：查询到x元素的根节点（教主）后，直接将x元素的上级改成根节点。

public int QuickFind(int x ) {
	// 如果x位置的值，等于x，说明x就是教主
	if (x == array[x]) {
		return array[x];
	}
	// 如果不是，查x位置的值的上级，等递归回退的时候，把x的上级改成根节点
	return array[x] = find(array[x]);
}

也就是说，第一次find元素x，是没有压缩路径的，第二次才是优化后的效果

3、并查集union的优化：权重标记

和find优化属于同一思想，union两个集合时，防止树过高，比如合并：

在这里插入图片描述
如果这么连，树过高：

在这里插入图片描述
比较两棵树的高度，左边为2，右边为3，因此，高的树原地不动，继续做老大，低的树靠过去，union后的效果：

在这里插入图片描述

核心思想：

在这里插入图片描述

整体代码如下，带权重的union参考：

public class UnionFind {

	const int  N=1005					//指定并查集所能包含元素的个数（由题意决定）
	int pre[N];     					//存储每个结点的前驱结点的数组 
	int rank[N];    					//树的高度，权重
	
	void init(int n) {     				//初始化函数，对录入的 n个结点进行初始化 
	    for(int i = 0; i < n; i++){
	        pre[i] = i;     			//每个结点的上级都是自己 
	        rank[i] = 1;    			//每个结点构成的树的高度为 1 
	    } 
	}

	int find(int x) {
     	//查找结点 x的根结点 
		if (pre[x] == x) { 
			return x ;					//递归出口：x的上级为 x本身，则 x为根结点 
		}  		
	    return find(pre[x]); 			//递归查找 
	} 
	 
	int findQucik(int x) {     			//改进查找算法：完成路径压缩，将 x的上级直接变为根结点，那么树的高度就会大大降低 
	    if (pre[x] == x) {
	    	return x;					//递归出口：x的上级为 x本身，即 x为根结点 
	    }
	    return pre[x] = find(pre[x]);   //此代码相当于先找到根结点 rootx，然后 pre[x]=rootx 
	} 
	
	bool isSame(int x, int y) {     	//判断两个结点是否连通 
	    return find(x) == find(y);  	//判断两个结点的根结点（即代表元）是否相同 
	}
	
	void union(int x,int y) {
	    int rootx = find(x);			//寻找 x的代表元
	    int rooty = find(y);			//寻找 y的代表元
	    if(rootx != rooty) {			//如果 x和 y的代表元一致，说明他们共属同一集合，则不需要合并
		    if(rank[rootx] > rank[rooty]) {		//如果 x的高度大于 y，则令 y的上级为 x
		    	pre[rooty] = rootx;
		    } else if (rank[rootx] < rank[rooty]) {
		    	pre[rootx] = rooty;		//让 x的上级为 y
		    } else {
		    	pre[rooty] = rootx;	    								
		        rank[rootx] += 1;				//如果 x的高度和 y的高度相同，则令 y的高度加1					
			}
		}
	}
}