摘要
Title: 860. 染色法判定二分图
Tag: 二分图
Memory Limit: 64 MB
Time Limit: 1000 ms

860. 染色法判定二分图

题意

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
思路

二分图当且仅当图中不含奇数环，由于图中不含奇数环，所以染色过程中一定没用矛盾
染色法进行染色，通过DFS或BFS即可

代码

DFS会爆栈，还是要改成BFS
注意：

当想DFS遇到不符合的情况就一直return false时
即将dfs语句写在if里

def dfs():
  if not dfs():
    return False
  ···
  ···
  return True

'''
Author: NEFU AB-IN
Date: 2022-03-04 15:38:45
FilePath: \ACM\Acwing\860.py
LastEditTime: 2022-03-04 16:08:53
'''
import sys

sys.setrecursionlimit(1000000000)
N = int(1e5 + 10)
g = [[] for _ in range(N)]
st = [0] * N


def dfs(u, c):
    st[u] = c
    for v in g[u]:
        if st[v] == 0:
            if not dfs(v, 3 - c):
                return False
        elif st[v] == c:
            return False
    return True


n, m = map(int, input().split())
for i in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

flag = 1
for i in range(n):
    if st[i] == 0:
        if not dfs(i, 1):
            flag = 0
            break
if flag:
    print("Yes")
else:
    print("No")

BFS

'''
Author: NEFU AB-IN
Date: 2022-03-04 22:37:00
FilePath: \ACM\Acwing\860.1.py
LastEditTime: 2022-03-04 23:00:45
'''
N = int(1e5 + 10)
st = [0] * N
g = [[] for _ in range(N)]

from collections import deque


def bfs(s):
    q = deque()
    q.appendleft(s)
    st[s] = 1
    while q:
        u = q.pop()
        for v in g[u]:
            if not st[v]:
                st[v] = 3 - st[u]
                q.appendleft(v)
            elif st[v] == st[u]:
                return False
    return True


n, m = map(int, input().split())
for i in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

flag = 1
for i in range(1, n + 1):
    if not st[i]:
        if not bfs(i):
            flag = 0
            break

if flag == 1:
    print("Yes")
else:
    print("No")

860. 染色法判定二分图

题意

思路

代码