题目：
给定一组 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 <= 20000 <= dislikes.length <= 104dislikes[i].length == 21 <= dislikes[i][j] <= nai < bidislikes中每一组都 不同
解题：
要解决这个问题，我们可以将其视为一个图着色问题。我们可以试图将这个社交网络图染成两种颜色，如果能成功染色，那么就能将这组人分成两组，使每个人所在的组别没有他们不喜欢的人。
基本思路是使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图。我们尝试给每个节点（即每个人）分配一个颜色（两个组之一），同时确保没有两个有冲突的人（dislikes 中提到的）拥有相同的颜色。
算法步骤：
-
建立图的邻接表: 创建一个图的表示形式，通常情况下是用邻接表。节点代表人，边代表人与人之间的
dislikes关系。 -
初始化颜色数组: 创建一个大小为
n+1的数组colors（因为人的编号是从1开始），用于记录每个人被分配到哪一组。未染色的人初始化为0，染色后为1或-1，分别代表两个不同的组。 -
深度优先遍历: 从第一个人开始，进行深度优先遍历。如果某个人还没有被染色，我们将其染色为1，然后对其不喜欢的每个人，如果他们未被染色则染成与之相反的颜色，即-1；如果已经被染色，则检查颜色是否相反。如果遇到冲突，即一个人的不喜欢列表中有与它同色的人，说明无法将所有人分成两组。
-
遍历所有的节点: 由于图可能是非连通的，那么需要从每一个未染色的节点开始新的遍历。如果任何一个节点不能被成功染色，则整个图不是二分图。
-
返回结果: 如果所有人都能被染色而没有冲突，那么就返回
true，否则返回false。
详细分析：
示例 1：
输入：n = 4, dislikes = [[1,2],[1,3],[2,4]]
输出：true
我们可以把这个图表示为以下的邻接表：
1: [2, 3]
2: [1, 4]
3: [1]
4: [2]
通过图染色方法，我们可以尝试这样分组：
- 为节点1染色为颜色A。然后，节点2和节点3染色为颜色B（因为 1 不喜欢 2 和 3）。
- 接着，节点4染色为颜色A（因为 2 不喜欢 4）。
那么分组会是：
- 组1：1, 4
- 组2：2, 3
这样的分组是可行的，因此返回 true。
示例 2：
输入：n = 3, dislikes = [[1,2],[1,3],[2,3]]
输出：false
邻接表表示为：
1: [2, 3]
2: [1, 3]
3: [1, 2]
尝试图染色方法：
- 为节点1染色为颜色A。然后，节点2和节点3染色为颜色B（因为 1 不喜欢 2 和 3）。
- 但是，节点2和节点3之间也是不喜欢关系，所以它们不可以是相同颜色。
因此，无法形成符合要求的两组，返回 false。
示例 3：
输入：n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出：false
邻接表表示为：
1: [2, 5]
2: [1, 3]
3: [2, 4]
4: [3, 5]
5: [1, 4]
尝试图染色方法：
- 为节点1染色为颜色A。然后，节点2和节点5染色为颜色B。
- 接着，节点3染色为颜色A（因为2不喜欢3）。
- 继续，节点4染色为颜色B（因为3不喜欢4）。
- 但节点4和节点5有不喜欢关系，但他们都是颜色B，这不符合要求。
因此，无法形成符合要求的两组，返回 false。
提示：
-
1 <= n <= 2000：
- 意味着节点数最多为2000，处理这么多节点是可行的，因此算法复杂度需要是多项式时间复杂度。
-
0 <= dislikes.length <= 10^4：
- 表示最多有10,000对不喜欢的关系，需要有效处理这些信息。
-
每个
dislikes[i]数组的长度为2：- 每个数组元素有且只有两个元素，表示两人之间的关系。
-
1 <= dislikes[i][j] <= n：
- 所有编号都是有效的，会在1到n之间。
-
ai < bi：
- 命名习惯，但对于图的表示，不重要。
-
dislikes中每一组都不同：
- 保证每对关系是唯一的，从而不用担心重复关系。
解题流程图：
+------------------------------------------------+
| 输入: n = 人数, dislikes = 不喜欢的对记录数组 |
+------------------------------------------------+
|
V
+------------------------------------------------+
| 建立图的邻接表 using dislikes |
| graph = [[], [], ..., []] (长度为n的空列表集合) |
+------------------------------------------------+
|
V
+------------------------------------------------+
| 将 dislikes 中的关系加入邻接表 |
| 对每个元素 [a, b] in dislikes: |
| graph[a].append(b) |
| graph[b].append(a) |
+------------------------------------------------+
|
V
+------------------------------------------------+
| 初始化colors数组: colors = [0]*(n+1) |
+------------------------------------------------+
|
V
+------------------------------------------------+
| 对每个节点 i 从 1 到 n: |
| 若 colors[i] == 0 并且 !isValidColor(i, 1): |
| 返回 False |
| |
| 若所有节点都成功染色: |
| 返回 True |
+------------------------------------------------+
|
V
+------------------------------------------------+
| 函数 isValidColor(graph, colors, node, color) |
+------------------------------------------------+
| 若 colors[node] != 0: |
| 返回 colors[node] == color |
| |
| colors[node] = color |
| |
| 对 graph[node] 中的每个相邻节点 next: |
| 若 !isValidColor(graph, colors, next, -color): |
| 返回 False |
| |
| 返回 True |
+------------------------------------------------+代码：
import java.util.ArrayList;
import java.util.List;
public class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) {
// 创建图的邻接表
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
// 填充邻接表
for (int[] pair : dislikes) {
graph.get(pair[0]).add(pair[1]);
graph.get(pair[1]).add(pair[0]);
}
int[] colors = new int[n + 1];
// 对每个节点尝试进行着色
for (int i = 1; i <= n; i++) {
if (colors[i] == 0 && !isValidColor(graph, colors, 1, i)) {
return false;
}
}
return true;
}
private boolean isValidColor(List<List<Integer>> graph, int[] colors, int color, int node) {
if (colors[node] != 0) {
// 如果当前节点已有颜色，检查是否与要染的颜色相同
return colors[node] == color;
}
colors[node] = color; // 给节点染色
// 遍历所有不喜欢当前节点的人
for (int next : graph.get(node)) {
if (!isValidColor(graph, colors, -color, next)) {
return false;
}
}
return true;
}
}知识点解析：
-
图的表示：代码使用邻接表来表示图。邻接表是图的一种表示方法，其中每个节点的所有临边都以列表的形式表示。在这个问题中，图是由“不喜欢”关系定义的，其中每一对相互不喜欢的人被表示为图中的一条边。
-
深度优先搜索（DFS）：这是一种用于遍历或搜索树或图的结构的算法。在这个问题中，DFS用于递归地检查能否为图中的每个节点着色（分组），同时满足给定的“不喜欢”条件。
-
递归：
isValidColor函数是递归的，它为节点着色并为所有邻接节点调用自身以着相反颜色。递归是解决这类问题的一个有效方法，因为它允许我们重用相同的逻辑来探索图中的所有节点。 -
颜色数组：数组
colors存储每个人的组别，有三种可能的值：0表示未着色，1表示一种颜色，-1表示另一种颜色。通过这种方法来追踪每个节点的状态，并确保任何时候连通的节点不会着相同的颜色。
| 知识点 | 描述 | 代码示例 |
|---|---|---|
| 图的表示 | 使用邻接表表示图的节点和它们之间的边。 | List<List<Integer>> graph = new ArrayList<>(); |
| 深度优先搜索（DFS） | 一个递归遍历算法，用于在图结构中探索节点。 | private boolean isValidColor(List<List<Integer>> graph, int[] colors, int color, int node) |
| 递归 | 一个函数调用自己来解决问题的方法。 | if (!isValidColor(graph, colors, -color, next)) |
| 颜色数组 | 一个数组，用来追踪每个图节点的颜色状态。 | int[] colors = new int[n + 1]; |
| 条件语句 | 用于根据当前状态决策下一步如何执行。 | if (colors[node] != 0) |
| 循环 | 通过循环访问所有相邻的节点和它们的边。 | for (int next : graph.get(node)) |
