Java 算法导论版本
之前由于在cousera上面看过princeton算法的视频,里面上来讲的就是并查集,并且也给出了代码。当时还举了很多
生活实际中可以用到的例子,所以我就照着敲了敲代码,之后也就一直按着当时给的模版敲了,这里给一下那里面的代码。
视频参考:
https://www.coursera.org/learn/algorithms-part1/lecture/fjxHC/dynamic-connectivity
import java.io.*;
public class Main {
static class UF {
int[] id;
int[] sz;
public UF(int n) {
id = new int[n];
sz = new int[n];
for (int i = 0; i < n; i++) {
id[i] = i;
sz[i] = 1;
}
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int find(int p) {
int root = p;
while (root != id[root]) {
root = id[root];
}
while (p != id[p]) {
int newp = id[p];
id[p] = root;
p = newp;
}
return root;
}
public void union(int p, int q) {
int i = find(p);
int j = find(q);
if (i == j) return;
if (sz[i] <= sz[j]) {
id[i] = id[j];
sz[j] += sz[i];
} else {
id[j] = id[i];
sz[i] += sz[j];
}
}
}
public static void main (String[] arg) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]), m = Integer.parseInt(s1[1]);
UF uf = new UF(n);
while(m-- > 0) {
String[] in = br.readLine().split(" ");
int n1 = Integer.parseInt(in[1]) - 1, n2 = Integer.parseInt(in[2]) - 1;
if (in[0].equals("M")) {
uf.union(n1, n2);
} else {
if (uf.connected(n1,n2)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
}
}