并查集

本篇文章参考《啊哈!算法》。所有算法相关文章仅供自己平时翻阅,不会写什么解释,所以大家慎入!

测试数据:

1
2
3
4
5
6
7
8
9
10
9 9
0 1
2 3
4 1
3 5
1 5
7 6
8 6
0 5
1 3

程序代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

/**
* Created by JING on 2018/1/30.
*/
public class UnionFind {
private static int[] arr;

public static void main(String[] args) {
Scanner scanner = null;
try {
scanner = new Scanner(new FileInputStream("D:\\git-work\\Algorithm\\UnionFind\\src\\UnionFind.txt"));
//m 表示输入数据条数
int m = scanner.nextInt();
//n 表示罪犯人数(编号0~n-1)
int n = scanner.nextInt();
init(n);
for (int i = 0; i < m; i ++) {
merge(scanner.nextInt(), scanner.nextInt());
}
for (int i = 0; i < m; i ++) {
System.out.println("arr[" + i + "] = " + arr[i]);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}

/**
* @param n 强盗人数
*/
private static void init(int n) {
arr = new int[n];
Arrays.fill(arr, -1);
for (int i = 0; i < n; i ++) {
arr[i] = i;
}
}

/**
* 查找 t 的老大的编号
* @param t
* @return
*/
private static int getParent(int t) {
if (arr[t] == t) {
return t;
} else {
arr[t] = getParent(arr[t]);
return arr[t];
}
}

/**
* 合并 t1 和 t2
* @param t1
* @param t2
*/
private static void merge(int t1, int t2) {
int u = getParent(t1);
int v = getParent(t2);
if (u != v) {
if (v < u) {
int temp = v;
v = u;
u = temp;
}
arr[v] = u;
}
}

/**
* 判断 t1 和 t2 是否在同一个集合中,需在所有合并动作完成后调用
* @param t1
* @param t2
* @return
*/
private static boolean atSameGroup(int t1, int t2) {
return arr[t1] == arr[t2];
}

}
文章目录
  1. 1. 测试数据:
  2. 2. 程序代码:
|