给定一个没有重复值的整形数组arr,初始时认为arr中每一个数各自都是一个单独的集合。请设计一种叫UnionFind的结构,并提供以下两个操作。
boolean isSameSet(int a, int b): 查询a和b这两个数是否属于一个集合
void union(int a, int b): 把a所在的集合与b所在的集合合并在一起,原本两个集合各自的元素以后都算作同一个集合
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashMap;
import java.util.Map;
public class Main {
private static final StreamTokenizer TOKENIZER =
new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
private static int nextInt() {
try {
TOKENIZER.nextToken();
} catch (IOException e) {
e.printStackTrace();
}
return (int) TOKENIZER.nval;
}
public static void main(String[] args) {
int n = nextInt();
int m = nextInt();
UnionSet<Integer> unionSet = new UnionSet<>();
for (int i = 1; i <= n; ++i) {
unionSet.add(i);
}
while (m-- > 0) {
int op = nextInt();
int a = nextInt();
int b = nextInt();
if (op == 1) {
System.out.println(unionSet.inSameSet(a, b) ? "Yes" : "No");
} else {
unionSet.union(a, b);
}
}
}
}
class UnionSet<V> {
private Map<V, V> parentMap = new HashMap<>();
private Map<V, Integer> sizeMap = new HashMap<>();
public void add(V v) {
parentMap.put(v, v);
sizeMap.put(v, 1);
}
public void build(V[] arr) {
if (arr == null || arr.length == 0) {
return;
}
for (V item : arr) {
parentMap.put(item, item);
sizeMap.put(item, 1);
}
}
public boolean inSameSet(V v1, V v2) {
V parentV1 = find(v1);
V parentV2 = find(v2);
if (parentV1 == null || parentV2 == null) {
return false;
}
return parentV1 == parentV2;
}
private V findPlus(V x) {
V root = parentMap.get(x);
while (root != parentMap.get(root)) {
root = parentMap.get(root);
}
while (x != root) {
V father = parentMap.get(x);
parentMap.put(x, root);
x = father;
}
return root;
}
public V find(V x) {
V parent = parentMap.get(x);
if (parent == x) {
return parent;
}
parent = find(parent);
parentMap.put(x, parent);
return parent;
}
public void union(V v1, V v2) {
V parentV1 = find(v1);
V parentV2 = find(v2);
if (parentV1 == null || parentV2 == null || parentV1 == parentV2) {
return;
}
int sizeV1 = sizeMap.get(parentV1);
int sizeV2 = sizeMap.get(parentV2);
if (sizeV1 >= sizeV2) {
parentMap.put(parentV2, parentV1);
sizeMap.put(parentV1, sizeV1 + sizeV2);
sizeMap.remove(parentV2);
} else {
parentMap.put(parentV1, parentV2);
sizeMap.put(parentV2, sizeV1 + sizeV2);
sizeMap.remove(parentV1);
}
}
public int size() {
return sizeMap.size();
}
}
class Union {
private int[] parent;
private int[] size;
public Union(int n) {
parent = new int[n + 1];
size = new int[n + 1];
for (int i = 1; i <= n; ++i) {
parent[i] = i;
size[i] = 1;
}
}
public int find(int x) {
int p = parent[x];
if (p == x) {
return p;
}
p = find(p);
parent[x] = p;
return p;
}
public boolean inSameSet(int a, int b) {
return find(a) == find(b);
}
public void union(int a, int b) {
int p1 = find(a);
int p2 = find(b);
if (p1 == p2) {
return;
}
if (size[p1] >= size[p2]) {
parent[p2] = p1;
size[p1] = size[p1] + size[p2];
} else {
parent[p1] = p2;
size[p2] = size[p1] + size[p2];
}
}
}