版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434803
挑战程序竞赛系列（10）：2.4并查集
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
- POJ 2236: Wireless Network
- POJ 1703: Find them, Catch them
- AOJ 2170: Marked Ancestor
POJ 2236: Wireless Network
写个Union，在距离范围内的电脑可以认为是同属于一个集合，进行合并。当然还需要注意电脑当前的状态是否修复，如果未修复，即使在指定距离内，也不能合并。
即使做了些状态记录，Java代码还是慢啊。
代码如下：
代码语言：javascript复制public class SolutionDay15_L2236 {
static class Union{
int[] id;
int[] sz;
public Union(int size){
id = new int[size];
sz = new int[size];
for (int i = 0; i < size; i){
id[i] = i;
sz[i] = 1;
}
}
public void union(int i, int j){
int p = find(i);
int q = find(j);
if (p == q) return;
if (sz[p] < sz[q]){
id[p] = q;
sz[q] = sz[p];
}
else{
id[q] = p;
sz[p] = sz[q];
}
}
public int find(int i){
while (id[i] != i){
i = id[i];
}
return i;
}
public boolean connect(int i, int j){
return find(i) == find(j);
}
}
private static boolean distance(int[] c1, int[] c2, int d){
int x = c1[0] - c2[0];
int y = c1[1] - c2[1];
return (x * x y * y) <= d * d;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] n = in.nextLine().trim().split(" ");
int N = Integer.parseInt(n[0]);
int D = Integer.parseInt(n[1]);
boolean[] status = new boolean[N];
boolean[][] distance = new boolean[N][N];
Union union = new Union(N);
int[][] coord = new int[N][2];
for (int i = 0; i < N; i){
n = in.nextLine().trim().split(" ");
coord[i][0] = Integer.parseInt(n[0]);
coord[i][1] = Integer.parseInt(n[1]);
}
for (int i = 0; i < N; i){
for (int j = i 1; j < N; j){
if(distance(coord[i], coord[j], D)){
distance[i][j] = true;
distance[j][i] = true;
}
}
}
while (in.hasNextLine()){
String[] operates = in.nextLine().trim().split(" ");
if (operates[0].equals("O")){
int c = Integer.parseInt(operates[1]) - 1;
status[c] = true;
for (int j = 0; j < N; j){
if (j == c) continue;
if (status[j] && distance[j][c])
union.union(c, j);
}
}
if (operates[0].equals("S")){
int c1 = Integer.parseInt(operates[1]) - 1;
int c2 = Integer.parseInt(operates[2]) - 1;
System.out.println(union.connect(c1, c2) ? "SUCCESS" : "FAIL");
}
}
in.close();
}
}POJ 1703: Find them, Catch them
思路：
copy一团罪犯，敌人的敌人是我们的朋友。
代码如下：
代码语言：javascript复制public class SolutionDay15_L1703 {
static class Union{
int[] id;
int[] sz;
public Union(int size){
id = new int[size];
sz = new int[size];
for (int i = 0; i < size; i){
id[i] = i;
sz[i] = 1;
}
}
public int find(int i){
while (id[i] != i){
i = id[i];
}
return i;
}
public boolean same(int i, int j){
return find(i) == find(j);
}
public void union(int i, int j){
int p = find(i);
int q = find(j);
if (p == q) return;
if (sz[p] < sz[q]){
id[p] = q;
sz[q] = sz[p];
}
else{
id[q] = p;
sz[p] = sz[q];
}
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for (int i = 0; i < T; i){
int N = in.nextInt();
int M = in.nextInt();
Union u = new Union(2 * N);
for (int j = 0; j < M; j){
String opera = in.next();
int c1 = in.nextInt() - 1;
int c2 = in.nextInt() - 1;
if (opera.equals("A")){
if (u.same(c1, c2)){
System.out.println("In the same gang.");
}
else if (u.same(c1, c2 N)){
System.out.println("In different gangs.");
}
else{
System.out.println("Not sure yet.");
}
}
else{
u.union(c1, c2 N);
u.union(c1 N, c2);
}
}
}
in.close();
}
}AOJ 2170: Marked Ancestor
非常easy，dfs找父结点即可，如果mark，则把该结点的父亲改为自己即可。
代码如下：
代码语言：javascript复制 public static int find(int i){
while (i != id[i]) i = id[i];
return i;
}
static int[] id;
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
while (true){
int N = in.nextInt();
int Q = in.nextInt();
if (N == 0 && Q == 0) break;
id = new int[N];
for (int i = 1; i < N; i){
int p = in.nextInt() - 1;
id[i] = p;
}
long sum = 0;
for (int i = 0; i < Q; i){
String opera = in.next();
int c = in.nextInt() - 1;
if (opera.equals("Q")){
sum = (find(c) 1);
}
else{
id[c] = c;
}
}
System.out.println(sum);
}
}
