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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://howardyangemail.gitbook.io/decode-leetcode/graph/bipartite-graph.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.