【图, DFS】可能的二分法

题目

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 <= 10^4
• dislikes[i].length == 2
• 1 <= dislikes[i][j] <= n
• ai < bi
• dislikes 中每一组都 不同

解题

方法一：DFS

思路

把人之间的不喜欢关系构建成一个无向图，顶点表示每个人，每条边表示两个顶点之间有不喜欢关系，不能分在同一组。使用邻接表(graph)（长度为n+1，索引为 0 的元素忽略）表示这个图，再创建一个映射表(vertexToGroup)存储每个顶点对应着它们被分到的组，其中只有两个组可供选择，0 表示一个组，1 又表示另一个组。

对于每个顶点，递归地将其它加入组（其中第一个元素可以加入任意一个组，对结果没有影响）：

• 如果当前顶点已经被分配了某组，则比较它「现在所在的组」和「由参数传进来它应该进的组(group)」是否相同，如果不同，则返回 false 表示该节点的归属出现了矛盾，不能用这种方法分组。否则返回 true 表示该节点的分组是正确的。
• 如果顶点还未被分配组，就将其先分配到「由参数传进来它应该进的组」中，然后对遍历邻接表中该元素对应的集合，把所有和它不能进同一组的顶点全部递归地分配到其他组。如果分配的过程中出现矛盾，也返回 false。如果所有顶点都正常分配完则返回 true 。

代码

class Solution {
    private List<Integer>[] graph;
    private Map<Integer, Integer> vertexToGroup;

    public boolean possibleBipartition(int n, int[][] dislikes) {
        graph = (LinkedList<Integer>[]) new LinkedList[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new LinkedList<>();
        for (int[] dislike : dislikes) {
            graph[dislike[0]].add(dislike[1]);
            graph[dislike[1]].add(dislike[0]);
        }
        vertexToGroup = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            if (!vertexToGroup.containsKey(i) && !dfs(i, 0)) return false;
        }
        return true;
    }

    private boolean dfs(int vertex, int group) {
        if (vertexToGroup.containsKey(vertex)) {
            return vertexToGroup.get(vertex) == group;
        }
        vertexToGroup.put(vertex, group);
        for (int dislike : graph[vertex]) {
            if (!dfs(dislike, group ^ 1)) return false;
        }
        return true;
    }
}

方法二：并查集

思路

我们知道对于 $dislikes[i] = (a, b)$ 而言，点 $a$ 和点 $b$ 必然位于不同的集合中，同时由于只有两个候选集合，因此这样的关系具有推断性：即对于 $(a, b)$ 和 $(b, c)$ 可知 $a$ 和 $c$ 位于同一集合。

因此，我们可以对于每个点 $x$ 而言，建议一个反向点 $x + n$：若点 $x$ 位于集合 $A$ 则其反向点 $x + n$ 位于集合 $B$，反之同理。

基于此，我们可以使用「并查集」维护所有点的连通性：边维护边检查每个 $dislikes[i]$ 的联通关系，若 $dislikes[i] = (a, b)$ 联通，必然是其反向点联通所导致，必然是此前的其他 $dislikes[j]$ 导致的关系冲突，必然不能顺利划分成两个集合，返回 $false$，否则返回 $true$。

参考：【宫水三叶】判定二分图模板题 - 反向点+并查集

代码

class Solution {
    int[] root;

    void union(int p, int q) {
        root[find(p)] = find(q);
    }

    int find(int x) {
        return x == root[x] ? x : (root[x] = find(root[x]));
    }

    boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    public boolean possibleBipartition(int n, int[][] dislikes) {
        root = new int[n * 2 + 1];
        for (int i = 1; i <= n * 2; ++i) root[i] = i;
        for (int[] dislike : dislikes) {
            int a = dislike[0], b = dislike[1];
            if (isConnected(a, b)) return false;
            union(a, b + n);
            union(b, a + n);
        }
        return true;
    }
}

并查集模板：路径压缩优化的并查集

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        UnionFind uf = new UnionFind(n * 2 + 1);
        for (int[] dislike : dislikes) {
            int a = dislike[0], b = dislike[1];
            if (uf.isConnected(a, b)) return false;
            uf.union(a, b + n);
            uf.union(b, a + n);
        }
        return true;
    }

    static class UnionFind {
        private int[] root;

        public UnionFind() { }
        
        public UnionFind(int size) {
            root = new int[size];
            for (int i = 0; i < size; ++i) root[i] = i;
        }
        
        public int find(int n) {
            return n == root[n] ? n : (root[n] = find(root[n]));
        }

        public void union(int p, int q) {
            root[find(p)] = find(q);
        }

        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }
    }

}