用java 写出并查集的代码
时间: 2023-03-16 22:43:52 浏览: 78
import java.util.HashMap;
class UnionFind {
private HashMap<Integer, Integer> parent = new HashMap<>(); public UnionFind(int n) {
for (int i = 0; i < n; i++) {
parent.put(i, i);
}
} public int find(int x) {
int parentX = parent.get(x);
if (parentX == x) {
return x;
}
int ancestor = find(parentX);
// 路径压缩
parent.put(x, ancestor);
return ancestor;
} public void union(int x, int y) {
int ancestorX = find(x);
int ancestorY = find(y);
if (ancestorX == ancestorY) {
return;
}
parent.put(ancestorX, ancestorY);
}
}答案:我可以为您提供一段用Java写出并查集的代码:
import java.util.HashMap;
class UnionFind {
private HashMap<Integer, Integer> parent = new HashMap<>(); public UnionFind(int n) {
for (int i = 0; i < n; i++) {
parent.put(i, i);
}
} public int find(int x) {
int parentX = parent.get(x);
if (parentX == x) {
return x;
}
int ancestor = find(parentX);
// 路径压缩
parent.put(x, ancestor);
return ancestor;
} public void union(int x, int y) {
int ancestorX = find(x);
int ancestorY = find(y);
if (ancestorX == ancestorY) {
return;
}
parent.put(ancestorX, ancestorY);
}
}