c++:
class UnionFind{
vector<int> root; // 根节点
vector<int> rank; // 节点高度
public:
UnionFind(int size){
root.resize(size);
rank.resize(size);
for(int i=0;i<size;++i){
root[i]=i;
rank[i]=1;
}
}
void unionNum(int x,int y){
int rootX=find(x);
int rootY=find(y);
// 两个根节点相等的话啥也不干,不相等则union
if(rootX!=rootY){
if(rank[rootX]>rank[rootY]){
root[rootY]=rootX;
}else if(rank[rootX]<rank[rootY]){
root[rootX]=rootY;
}else{
root[rootY] = rootX;
rank[rootX]++;
}
}
}
int find(int x){
if(x==root[x]){
return x;
}
return root[x]=find(root[x]);
}
bool connect(int x, int y){
return find(x)==find(y);
}
}
java:
// UnionFind.class
public class UnionFind {
int root[];
// 添加了 rank 数组来记录每个顶点的高度,也就是每个顶点的「秩」
int rank[];
public UnionFind(int size) {
root = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
root[i] = i;
rank[i] = 1; // 一开始每个顶点的初始「秩」为1,因为它们只有自己本身的一个顶点。
}
}
// 此处的 find 函数与路径压优化缩版本的 find 函数一样。
public int find(int x) {
if (x == root[x]) {
return x;
}
return root[x] = find(root[x]);
}
// 按秩合并优化的 union 函数
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
root[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
root[rootX] = rootY;
} else {
root[rootY] = rootX;
rank[rootX] += 1;
}
}
};
public boolean connected(int x, int y) {
return find(x) == find(y);
}
}
// App.java
// 测试样例
public class App {
public static void main(String[] args) throws Exception {
UnionFind uf = new UnionFind(10);
// 1-2-5-6-7 3-8-9 4
uf.union(1, 2);
uf.union(2, 5);
uf.union(5, 6);
uf.union(6, 7);
uf.union(3, 8);
uf.union(8, 9);
System.out.println(uf.connected(1, 5)); // true
System.out.println(uf.connected(5, 7)); // true
System.out.println(uf.connected(4, 9)); // false
// 1-2-5-6-7 3-8-9-4
uf.union(9, 4);
System.out.println(uf.connected(4, 9)); // true
}
}
网友评论