基本实现

任务：

  维护多个不相交的集合，支持两种操作：合并两个集合，查询一个元素所在的集合。

说明：

  维护一个森林，每一棵树都代表一个集合，树根元素为这个集合的代表元。利用数组father[]查询记录每个元素的父亲节点。

查询一个元素所处集合时，只需不断寻找父节点，即可找到该元素所处集合的代表元。

合并两个集合时，先找到两个集合代表元x,y,然后令father[x]=y即可。

优化：

  路径压缩，沿着树根的路径找到元素a所在集合代表元b后，对这条路径上的所有元素x，令father[a]=b;

  按rank启发式合并，对于每个集合维护一个rank值，每次将rank较小的集合合并到rank较大的集合，合并两个相同的集合时rank=rank+1。

  根据不同情况也可以添加集合大小等属性。

public class union_find {private int[] father;private int[] rank;//初始化public union_find(int n) {father = new int[n];rank = new int[n];for (int i = 0; i < n; i++) {father[i] = i;rank[i] = 1;}}//查询在那个集合int find(int v) {return father[v] = father[v] == v ? v : find(father[v]);}//合并void merge(int x, int y) {int a = find(x);int b = find(y);if (rank[a] < rank[b]) {father[a] = b;} else {father[b] = a;if (rank[a] == rank[b]) {rank[a]++;}}}}

例题

省份数量https://leetcode.cn/problems/number-of-provinces/description/代码：

class Solution {public int findCircleNum(int[][] isConnected) {if(isConnected==null||isConnected.length == 0){return 0;}int n=isConnected.length;union_find uf=new union_find(n);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if(isConnected[i][j]==1){uf.merge(i,j);}}}int cnt=0;for (int i = 0; i < n; i++) {if(uf.father[i]==i){cnt++;}}return cnt;}public class union_find {private int[] father;private int[] rank;//初始化public union_find(int n) {father = new int[n];rank = new int[n];for (int i = 0; i < n; i++) {father[i] = i;rank[i] = 1;}}//查询在那个集合int find(int v) {return father[v] = father[v] == v ? v : find(father[v]);}//合并void merge(int x, int y) {int a = find(x);int b = find(y);if (rank[a] < rank[b]) {father[a] = b;} else {father[b] = a;if (rank[a] == rank[b]) {rank[a]++;}}}}}

 

剑指 Offer II 119. 最长连续序列https://leetcode.cn/problems/WhsWhI/description/

代码：

import java.util.HashMap;class Solution {public int longestConsecutive(int[] nums) {//存储下标和值Map<Integer,Integer>map=new HashMap<>();union_find uf=new union_find(nums.length);for (int i = 0; i < nums.length; i++) {if(map.containsKey(nums[i]))continue;if(map.containsKey(nums[i]-1)){uf.merge(i,map.get(nums[i]-1));}if(map.containsKey(nums[i]+1)){uf.merge(i,map.get(nums[i] + 1));}map.put(nums[i], i);}int size=0;for (int i = 0; i < nums.length; i++) {if(uf.father[i]==i){size=Math.max(size,uf.size[i]);}}return size;}public class union_find {private int[] father;private int[] size;//初始化public union_find(int n) {father = new int[n];size= new int[n];for (int i = 0; i < n; i++) {father[i] = i;size[i] = 1;}}//查询在那个集合int find(int v) {return father[v] = father[v] == v ? v : find(father[v]);}//合并void merge(int x, int y) {int a = find(x);int b = find(y);if(a==b)return;father[a]=b;size[b]+=size[a];}}
}