题目描述

Q：为什么有一层循环遍历每个点？
A：因为一个图是二分图，必须每个联通分量都是二分图。因此，考虑到整个图不是联通的情况下，遍历到每个联通分量。

样例

blablabla

Python代码

import queue
N = 100010
h = [-1]*N
ne = [0]*N*2
e = [0]*N*2
idx = 0
color = [0]*N

def add(x,y):
    global idx
    ne[idx] = h[x]
    h[x] = idx
    e[idx]  = y
    idx += 1 

if __name__ == '__main__':
    n,m = map(int,input().split())
    for i in range(m):
        u,v = map(int,input().split())
        add(u,v)
        add(v,u)
    q = queue.Queue()

    for i in range(1,n+1):
        if color[i] == 0:
            q.put([i,1])
            color[i] = 1 
        while not q.empty():
            node,c = q.get()
            head = h[node]
            while head!=-1:
                point = e[head]
                if color[point] == 0:
                    color[point] = 3-c
                    q.put([point,3-c])
                elif color[point] != 3-c:
                    print("No")
                    exit()

                head = ne[head]
    print('Yes')