【Day 30 】2023-12-15 - 886. 可能的二分法

[larscheng]

https://leetcode-cn.com/problems/possible-bipartition/

[larscheng]

思路

邻接矩阵建立dislike图，记录每个元素的分组情况，0-未分组，1-a组，-1-b组

代码

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<Integer>[] matrix = new ArrayList[n + 1];
        for (int i = 1; i < matrix.length; i++) {
            matrix[i] = new ArrayList(n + 1);
        }
        //邻接矩阵记录dislikes 矩阵中记录每行元素的dislike元素
        for (int[] item : dislikes) {
            matrix[item[0]].add(item[1]);
            matrix[item[1]].add(item[0]);
        }
        // 记录分组情况 0，-1，1
        int[] record = new int[n + 1];
        for (int i = 1; i < matrix.length ; i ++){
            if (record[i] == 0 && !dfs(matrix, record, i, 1)) {
                //未分组，分组失败
                return false;
            }
        }
        return true;
    }

    private boolean dfs(List<Integer>[] matrix, int[] record, int index, int group) {
        record[index] = group;
        //检查当前元素的所有dislike
        List<Integer> dislike = matrix[index];
        for (int i = 0; i < dislike.size() ; i++) {
            int num = dislike.get(i);
            // 已分组且同一组，直接返回失败
            if (record[num] == group) {
                return false;
            }
            // 没分组，dfs进行分组，扔进对立组
            if (record[num] == 0 && !dfs(matrix, record, num, group * -1)) {
                return false;
            }
        }
        return true;
    }
}

复杂度

• 时间复杂度：O(n+m)
• 空间复杂度：O(n)