> For the complete documentation index, see [llms.txt](https://howardyangemail.gitbook.io/decode-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://howardyangemail.gitbook.io/decode-leetcode/graph/bipartite-graph.md).

# Bipartite Graph

#### [785. Is Graph Bipartite?](https://leetcode.com/problems/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**.

```java
    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](https://leetcode.com/problems/possible-bipartition/)

```java
    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;
    }
```