백준 1707 - 이분 그래프 (파이썬)

Answer

from sys import stdin
from collections import deque

input = stdin.readline

def bfs(start):
    queue = deque([start])
    visited[start] = 1

    while queue:
        a = queue.popleft()

        for i in matrix[a]:
            if visited[i] == 0:
                visited[i] = -visited[a]
                queue.append(i)
            elif visited[i] == visited[a]:
                return False

    return True

for _ in range(int(input())):
    V, E = map(int, input().split())
    
    matrix = [[] for _ in range(V + 1)]
    visited = [0] * (V + 1)
    isTrue = True

    for __ in range(E):
        a, b = map(int, input().split())
        matrix[a].append(b)
        matrix[b].append(a)

    for i in range(1, V + 1):
        if visited[i] == 0:
            if not bfs(i):
                isTrue = False
                break
    
    print("YES" if isTrue else "NO")