Bipartite Graph

785. Is Graph Bipartite?

Use colors array to detect if the colors are correct. One side of the bipartite set as 1 and the other side as -1, unvisited nodes as 0. If the node is unvisited, color the node. Also use this method to detect if the color of the next node is the opposite as the color of the current node.

    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] colors = new int[n];
        for (int i = 0; i < n; i++) {
            if (colors[i] == 0 && !dfs(i, 1, colors, graph)) {
                return false;
            }
        }
        return true;
    }
    
    private boolean dfs(int curt, int color, int[] colors, int[][] graph) {
        if (colors[curt] != 0) {
            return colors[curt] == color;
        }
        colors[curt] = color;
        for (int next : graph[curt]) {
            if (!dfs(next, -color, colors, graph)) {
                return false;
            }
        }
        return true;
    }

886. Possible Bipartition

    int N;
    public boolean possibleBipartition(int N, int[][] dislikes) {
        this.N = N;
        int[] colors = new int[N];
        boolean[][] dis = new boolean[N][N];
        for (int[] d : dislikes) {
            dis[d[0] - 1][d[1] - 1] = true;
            dis[d[1] - 1][d[0] - 1] = true;
        }
        for (int i = 0; i < N; i++) {
            if (colors[i] == 0 && !dfs(i, 1, colors, dis)) {
                return false;
            }
        }
        return true;
    }
    
    private boolean dfs(int curt, int color, int[] colors, boolean[][] dis) {
        if (colors[curt] != 0) {
            return colors[curt] == color;
        }
        colors[curt] = color;
        for (int i = 0; i < N; i++) {
            if (curt == i) continue;
            if (dis[curt][i] && !dfs(i, -color, colors, dis)) return false;
        }
        return true;
    }