# 染色法判断是否为二分图

**二分图一定不存奇边环**

1. 初始化颜色数组（用0代表未被染色，用1表示其中一种颜色，用2代表其中另一种颜色）
2. 遍历节点（从第一个点开始），如果该点为被染色，则将其染成第一种颜色并且将相邻的点染成另外一种颜色
3. 如果相邻边已经染了色并且和该点颜色（A）相同，或者给相邻边染另外一种颜色（B）但给相邻边的相邻边染色（A）失败，则该图不是二分图

```python
# 二分图一定不存在奇边环
from collections import defaultdict

# n点的数量，m边的数量
n, m = [int(x) for x in input().split(" ")]

# 存储图
dd = defaultdict(set)

# color 染色数组
color = [0] * (n + 1)

for _ in range(m):
    a, b = [int(x) for x in input().split(" ")]
    dd[a].add(b)
    dd[b].add(a)


def dfs(u, c):
    color[u] = c
    for node in dd[u]:
        if not color[node]:
            if not dfs(node, 3 - c):
                return False
        elif color[node] == c:
            return False
    return True


flag = True
for i in range(1, n + 1):
    if not color[i]:
        if not dfs(i, 1):
            flag = False
            break

print(flag)
"""
IN:
4 4
1 3
1 4
2 3
2 4
OUT:
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://1005281342.gitbook.io/code-porter/suan-fa/er-fen-tu/1-ran-se-fa.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.