题目描述
染色法判定二分图的题解,Python解法,这里有两个要注意的点:
1. 由于DFS会TLE,所以改成BFS.
2. BFS从1开始只会遍历所在的连通分量,所以要循环所有st[i] = 0的点
样例
给一个多联通分量的样例
7 7
1 2
2 3
3 4
4 1
5 6
7 5
算法1
(BFS) $O(n+m)$
"""
AcWing 860. 染色法判定二分图
"""
import queue
N = 100010
M = 200010
n, m = map(int, input().split())
e, ne, h = [0] * M, [0] * M, [-1] * N
st = [0] * N
idx = 0
q = queue.Queue()
def add(x, y):
global idx
e[idx] = y
ne[idx] = h[x]
h[x] = idx
idx += 1
def bfs(i):
q.put([i, 1])
st[i] = 1
while not q.empty():
u, c = q.get()
i = h[u]
while i != -1:
j = e[i]
if not st[j]:
st[j] = 3 - c
q.put([j, 3 - c])
elif st[j] == c:
return False
i = ne[i]
return True
def solution():
for _ in range(m):
x, y = map(int, input().split())
add(x, y)
add(y, x)
flag = True
for i in range(1, n + 1):
if not st[i]:
if not bfs(i):
flag = False
if flag:
print('Yes')
else:
print('No')
if __name__ == '__main__':
solution()
我想请教一下,为什么按照Y总的模板做DFS会报错,但是用BFS就没事?
爆栈了
想问一下,bfs过程里把当前节点的邻接点放入队列中的操作为什么是在未染色的条件下,是为了应对环么?
因为已经染色的话就要和当前节点比较颜色是否相同了