-
Notifications
You must be signed in to change notification settings - Fork 417
/
Solution9.java
86 lines (81 loc) · 2.2 KB
/
Solution9.java
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
86
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @description:
*
* 给定一组 n 人(编号为 1, 2, ..., n), 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人,那么他们不应该属于同一组。
*
* 给定整数 n 和数组 dislikes ,其中 dislikes[i] = [ai, bi] ,表示不允许将编号为 ai 和 bi的人归入同一组。当可以用这种方法将所有人分进两组时,返回 true;否则返回 false。
*
*
*
* 示例 1:
*
* 输入:n = 4, dislikes = [[1,2],[1,3],[2,4]]
* 输出:true
* 解释:group1 [1,4], group2 [2,3]
* 示例 2:
*
* 输入:n = 3, dislikes = [[1,2],[1,3],[2,3]]
* 输出:false
* 示例 3:
*
* 输入:n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
* 输出:false
*
*
* 提示:
*
* 1 <= n <= 2000
* 0 <= dislikes.length <= 104
* dislikes[i].length == 2
* 1 <= dislikes[i][j] <= n
* ai < bi
* dislikes 中每一组都 不同
*
*/
class Solution9 {
public boolean possibleBipartition(int n, int[][] dislikes) {
int[] fa = new int[n + 1];
Arrays.fill(fa, -1);
List<Integer>[] g = new List[n + 1];
for (int i = 0; i < n; ++i) {
g[i] = new ArrayList<Integer>();
}
for (int[] p : dislikes)
g[p[0]].add(p[1]);
g[p[1]].add(p[0]);
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < g[i].size(); ++j) {
unit(g[i].get(0), g[i].get(j), fa);
if (isconnect(i, g[i].get(j), fa)) {
return false;
}
}
}
return true;
}
public void unit(int x, int y, int[] fa) {
x = findFa(x, fa);
y = findFa(y, fa);
if (x == y) {
return ;
}
if (fa[x] <= fa[y]) {
int temp = x;
x = y;
y = temp;
}
fa[x] += fa[y];
fa[y] = x;
}
public boolean isconnect(int x, int y, int[] fa) {
x = findFa(x, fa);
y = findFa(y, fa);
return x == y;
}
public int findFa(int x, int[] fa) {
return fa[x] > 0 ? x : (fa[x] = findFa(fa[x], fa));
}
}