染色法判断是否为二分图

二分图一定不存奇边环

1. 初始化颜色数组（用0代表未被染色，用1表示其中一种颜色，用2代表其中另一种颜色）

2. 遍历节点（从第一个点开始），如果该点为被染色，则将其染成第一种颜色并且将相邻的点染成另外一种颜色

3. 如果相邻边已经染了色并且和该点颜色（A）相同，或者给相邻边染另外一种颜色（B）但给相邻边的相邻边染色（A）失败，则该图不是二分图

# 二分图一定不存在奇边环
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
"""