# 785. Is Graph Bipartite?

<https://leetcode.com/problems/is-graph-bipartite/description/>

## solution

> 判断二分图问题: 对图中每个点进行染色。二分图左边的部分置为-1，右边部分全部置为1，那么，任意相邻的两点颜色都不一样

* bfs

```python
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        colors = [0] * len(graph)

        for i in range(len(graph)):  # 注意这里每个点都要遍历一次
            if colors[i] != 0:
                continue

            queue = collections.deque()
            queue.append(i)
            colors[i] = 1  # 起始颜色都置为1

            while queue:
                node = queue.popleft()

                for adj in graph[node]:
                    if colors[adj] == colors[node]:
                        return False
                    if colors[adj] == 0:
                        colors[adj] = -colors[node]
                        queue.append(adj)
        return True
```

时间复杂度：O(∣V∣+∣E∣)\
空间复杂度：O(∣V∣)

* dfs

```python
```

## follow up

[1557. Minimum Number of Vertices to Reach All Nodes](https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/description/)

```python
class Solution:
    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        inorder = set()
        for pre, cur in edges:
            inorder.add(cur)
        return [i for i in range(n) if i not in inorder]
```

[886. Possible Bipartition](https://leetcode.com/problems/possible-bipartition/)

```python
class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        if n == 1 or not dislikes:
            return True

        blue = 1  # color = Eum(1, -1, 0)  # 原始为0
        graph = collections.defaultdict(list)
        color_dict = collections.defaultdict(int)

        for p1, p2 in dislikes:
            graph[p1].append(p2)
            graph[p2].append(p1)

        for i in range(1, n+1):
            if not color_dict[i] and not self.dfs(i, blue, graph, color_dict):
                return False
        return True

    def dfs(self, i, color, graph, color_dict):
        color_dict[i] = color
        for nei in graph[i]:
            if color_dict[nei] == color:
                return False

            if not color_dict[nei] and not self.dfs(nei, -color, graph, color_dict):
                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://longxingtan.gitbook.io/mle-interview/01_leetcode/08_bfs/785.-is-graph-bipartite.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.