算法（十二）并查集

用法

并查集模板 扁平化+小挂大

public static int MAXN = 1000001;

public static int[] father = new int[MAXN];

public static int[] size = new int[MAXN];

public static int[] stack = new int[MAXN];

public static int n;

public static void build() {
	for (int i = 0; i <= n; i++) {
		father[i] = i;
		size[i] = 1;
	}
}

// i号节点，往上一直找，找到代表节点返回！
public static int find(int i) {
	// 沿途收集了几个点
	int size = 0;
	while (i != father[i]) {
		stack[size++] = i;
		i = father[i];
	}
	// 沿途节点收集好了，i已经跳到代表节点了
	while (size > 0) {
		father[stack[--size]] = i;
	}
	return i;
}

public static boolean isSameSet(int x, int y) {
	return find(x) == find(y);
}

public static void union(int x, int y) {
	int fx = find(x);
	int fy = find(y);
	if (fx != fy) {
		// fx是集合的代表：拿大小
		// fy是集合的代表：拿大小
		if (size[fx] >= size[fy]) {
			size[fx] += size[fy];
			father[fy] = fx;
		} else {
			size[fy] += size[fx];
			father[fx] = fy;
		}
	}
}

模板2 只有扁平化

   public static int MAXN = 200001;

public static int[] father = new int[MAXN];

public static int n;

public static void build() {
	for (int i = 0; i <= n; i++) {
		father[i] = i;
	}
}

public static int find(int i) {
	if (i != father[i]) {
		father[i] = find(father[i]);
	}
	return father[i];
}

public static boolean isSameSet(int x, int y) {
	return find(x) == find(y);
}

public static void union(int x, int y) {
	father[find(x)] = find(y);
}

情侣牵手

leetcode 765

思路：把编号i，i+1的情侣看出编号为i/2的情侣对.按顺序每次让两个人的情侣编号两两进行合并，如果是一对情侣（情侣编号一样）那么集合个数不会变，如果不是比如第一个人属于第3对，第二个人属于第5对，那么把3，5合成一个集合。最后原始的情侣对数减去剩下的集合个数就是答案。

public static final int MAX = 31;

public static int[] father = new int[MAX];


public static void build(int m){
    for(int i =0;i<m;i++){
        father[i] = i;
    }
}

public static int find(int i) {
    if (i != father[i]) {
        father[i] = find(father[i]); // 路径压缩：递归更新父节点
    }
    return father[i];
}

public static void union(int x,int y){
    int fx = find(x);
    int fy = find(y);
    if(fx!=fy){
        father[fx] = fy;
        cnts--;
    }
}

public static int cnts;
public int minSwapsCouples(int[] row) {
    int n =row.length;
    cnts = n/2;
    build(n/2);
    for(int i =0;i<n;i+=2){
        union(row[i]/2,row[i+1]/2);
    }
    return n/2 - cnts;
}

相似字符串组

leetcode 839

思路：两层for循环每次判断两个字符串是否相似，相似的话就合并两个字符串的集合。最后返回集合个数即可。

   public static int MAXN = 301;

public static int[] father = new int[MAXN];

public static int sets;

public static void build(int n) {
	for (int i = 0; i < n; i++) {
		father[i] = i;
	}
	sets = n;
}

public static int find(int i) {
	if (i != father[i]) {
		father[i] = find(father[i]);
	}
	return father[i];
}

public static void union(int x, int y) {
	int fx = find(x);
	int fy = find(y);
	if (fx != fy) {
		father[fx] = fy;
		sets--;
	}
}

public static int numSimilarGroups(String[] strs) {
	int n = strs.length;
	int m = strs[0].length();
	build(n);
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (find(i) != find(j)) {
				int diff = 0;
				for (int k = 0; k < m && diff < 3; k++) {
					if (strs[i].charAt(k) != strs[j].charAt(k)) {
						diff++;
					}
				}
				if (diff == 0 || diff == 2) {
					union(i, j);
				}
			}
		}
	}
	return sets;
}

岛屿数量

leetcode 200

思路：其实这道题最优解是洪水填充，但是这里用并查集也可以做。把二维下标转为一维编号 i*n+j。然后依次遍历，如果自己是1 的话就 查看 右边 跟 下边是不是1，如果是的话就合并。最后返回集合个数即可。

public static void build(char[][] grid,int m,int n){
    cnts = 0;
    for(int i =0;i<m;i++){
        for(int j =0;j<n;j++){
            if(grid[i][j] == '1'){
                father[i*n+j] = i*n+j;
                cnts++;
            }
        }
    }
}

public static int find(int i){
    if(i != father[i]){
        father[i] = find(father[i]);
    }
    return father[i];
}

public static void union(int x,int y){
    int fx = find(x);
    int fy = find(y);
    if(fx!=fy){
        father[fx] = fy;
        cnts--;
    }
}

public int numIslands(char[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    build(grid,m,n);
    //合并岛屿
    for(int i =0;i<m;i++){
        for(int j =0;j<n;j++){
            if(grid[i][j] == '1'){
                //只用合并右边跟下边即可
                if( i!=m-1 && grid[i+1][j] == '1'){
                    union(i*n+j,(i+1)*n+j);
                }
                if( j!=n-1 && grid[i][j+1]=='1'){
                    union(i*n+j,i*n+j+1);
                }
            }
        }
    }
    return cnts;
}

专家开会

leetcode 2092

   public static int MAXN = 100001;

public static int[] father = new int[MAXN];

// 集合的标签信息 : 设置集合的一些属性
// 属性在哪？secret[代表元素] 代表集合的属性
public static boolean[] secret = new boolean[MAXN];

public static void build(int n, int first) {
	for (int i = 0; i < n; i++) {
		father[i] = i;
		secret[i] = false;
	}
	father[first] = 0;
	secret[0] = true;
}

public static int find(int i) {
	if (i != father[i]) {
		father[i] = find(father[i]);
	}
	return father[i];
}

public static void union(int x, int y) {
	int fx = find(x);
	int fy = find(y);
	if (fx != fy) {
		father[fx] = fy;
		secret[fy] |= secret[fx];
	}
}

// 会议排序 : m * log m
// 处理过程 : O(m)
// 收集答案 : O(n)
public static List<Integer> findAllPeople(int n, int[][] meetings, int first) {
	build(n, first);
	// {0 : 专家   1 : 专家编号   2 : 时刻}
	Arrays.sort(meetings, (a, b) -> a[2] - b[2]);
	int m = meetings.length;
	for (int l = 0, r; l < m;) {
		r = l;
		while (r + 1 < m && meetings[l][2] == meetings[r + 1][2]) {
			r++;
		}
		// l....r这些会议，一定是一个时刻
		for (int i = l; i <= r; i++) {
			union(meetings[i][0], meetings[i][1]);
		}
		// 有小的撤销行为，但这不是可撤销并查集
		// 只是每一批没有知道秘密的专家重新建立集合而已
		for (int i = l, a, b; i <= r; i++) {
			a = meetings[i][0];
			b = meetings[i][1];
			if (!secret[find(a)]) {
				father[a] = a;
			}
			if (!secret[find(b)]) {
				father[b] = b;
			}
		}
		l = r + 1;
	}
	List<Integer> ans = new ArrayList<>();
	for (int i = 0; i < n; i++) {
		if (secret[find(i)]) {
			ans.add(i);
		}
	}
	return ans;
}