题目大意：
可能的二分法
给定一组 N 人（编号为 1, 2, ..., N）， 我们想把每个人分进任意大小的两组。
每个人都可能不喜欢其他人，那么他们不应该属于同一组。
形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。
当可以用这种方法将每个人分进两组时，返回 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 <= 100001 <= dislikes[i][j] <= Ndislikes[i][0] < dislikes[i][1]- 对于
dislikes[i] == dislikes[j]不存在i != j
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=886
解题思路：
这道题是要用到dfs深度搜索的方法来解题。由于题目要求是将所有人分到两个组中，所以，我们可以先定义两个组为组一和组二，然后以任意一个人作为起始节点开始遍历。遍历的方法是查看当前人不喜欢的对象是谁，并将当前人和他不喜欢的对象们分在两个组中，然后再以其不喜欢的对象为节点继续查看其的不喜欢对象，直到遍历完所有的人。
在遍历过程中，如果遇到节点X已经被分过组，那么就要看当前要将X分入的组和之前的分组是否一致，如果出现矛盾，则可以结束遍历，直接返回false。如果一致，说明当前尚未出现矛盾点，另外注意，当前节点X之前已经被遍历过，因此不需要继续向下遍历。
以上就是写代码前应该考虑到的简单思路，但是有个问题，我们如何dps题目中给出的二维数组dislikes[][]呢？单纯看dislikes，它给出的仅仅是每两个人之间的局部关系，要做dps之前，我们需要将整体的关系网络描述出来才可以，因此，我们需要建立一个List<List<Integer>> dislikesMap对象，来保存每个人的不喜欢列表。List是有序数组，因此我们可以使用List的index来代表每个人，题目给出的人是从1开始起名的，所以，考虑到越界问题，dislikesMap的大小应该是人数加一(其中List[0]不保存数据，只是为了占位)。
举个例子，比如有1，2，3三个人，他们分别不喜欢除了自己以外的人，也就是说，1不喜欢2和3，2不喜欢1和3，3不喜欢1和2（无语的人际关系网。。。。）。那么， dislikesMap中保存的数据应为：
dislikesMap.get(0) = null;
dislikesMap.get(1) = {2, 3};
dislikesMap.get(2) = {1, 3};
dislikesMap.get(3) = {1, 2}; 接下来按照最早的思路dfs这个dislikesMap即可，看下完整代码：
List<List<Integer>> dislikesMap; // 保存每个人的不喜欢列表
int[] groupArray; // 保存分组信息，下表代表人名，值代表组名。
// 默认0为尚未分组，1为组1，2为组2
public boolean possibleBipartition(int N, int[][] dislikes) {
dislikesMap = new ArrayList<>();
dislikesMap.add(null); // 为了保持index和人名一致，将第一个元素置空
for (int n = 1; n <= N; n++) {
// 为每个人名先创建一个空数组
dislikesMap.add(new ArrayList<>());
}
for (int[] dis : dislikes) {
// 由于不喜欢关系是相互的，所以，将双方分别加入到对方的不喜欢列表中
dislikesMap.get(dis[0]).add(dis[1]);
dislikesMap.get(dis[1]).add(dis[0]);
}
// 与dislikesMap同样，为了保持index和人名一致，从index为1开始保存数据。
groupArray = new int[N + 1];
for (int n = 1; n <= N; n++) {
// 如果尚未将当前人分组，则dps当前人的关系树，分组失败返回false。
if (groupArray[n] == 0 && !dfs(n, 1)) {
return false;
}
}
// 全部无矛盾分组成功，返回true
return true;
}
// current为当前人，newGroupId为当前人被分到的组（1或者2）
private boolean dfs(int current, int newGroupId) {
// 将当前人current的组信息设置为newGroupId
groupArray[current] = newGroupId;
// 从dislikesMap中遍历当前人不喜欢的人列表
for (int next : dislikesMap.get(current)) {
// 该不被当前人喜欢的人尚未被分组
if (groupArray[next] == 0) {
// 尝试将这个不被喜欢的人next分到与当前人不同的组，
// 继续以next作为起点继续dfs，如果分组失败，返回false
if (!dfs(next, newGroupId == 1 ? 2 : 1)) {
return false;
}
} else if (groupArray[next] == newGroupId) {
// 如果该不被当前人喜欢的人已被分组，并且与当前人在同一组，
// 说明发生矛盾，即分组失败，返回false
return false;
}
}
// 全部分组成功
return true;
} 本题解法用时16ms
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-886-possible-bipartition-解题思路分析/