友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
886. 可能的二分法
给定一组 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中每一组都 不同
思路分析
| 感觉并查集也可以。回头试试。 |
-
一刷
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-08-26 23:25:17
*/
public boolean possibleBipartition(int n, int[][] dislikes) {
List<Integer>[] graph = new ArrayList[n];
Arrays.setAll(graph, k -> new ArrayList<>());
for (int[] d : dislikes) {
int x = d[0] - 1;
int y = d[1] - 1;
graph[x].add(y);
graph[y].add(x);
}
return isBipartite(graph);
}
private boolean isBipartite(List<Integer>[] graph) {
// colors[i] = 0 表示未访问节点 i
// colors[i] = 1 表示节点 i 为红色
// colors[i] = -1 表示节点 i 为蓝色
int[] colors = new int[graph.length];
for (int i = 0; i < graph.length; i++) {
if (colors[i] == 0 && !dfs(i, 1, graph, colors)) {
return false;
}
}
return true;
}
private boolean dfs(int x, int c, List<Integer>[] graph, int[] colors) {
colors[x] = c;
for (Integer y : graph[x]) {
if (colors[y] == c ||
colors[y] == 0 && !dfs(y, -c, graph, colors)) {
return false;
}
}
return true;
}