leetcode 886. Possible Bipartition 解题思路分析

题目大意：

可能的二分法

给定一组 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. 1 <= N <= 2000
2. 0 <= dislikes.length <= 10000
3. 1 <= dislikes[i][j] <= N
4. dislikes[i][0] < dislikes[i][1]
5. 对于 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

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-886-possible-bipartition-解题思路分析/