BOJ - 1707 - 이분 그래프

import sys
from collections import deque

def BFS(idx, check, arr):
    dq = deque()
    dq.append(idx)
    check[idx] = 1

    while dq:
        x = dq.popleft()
        for nx in arr[x]:
            if check[nx] == 0:
                check[nx] = -1 * check[x]
                dq.append(nx)

            elif check[nx] == check[x]:
                return 1
    return 0

def solution():
    K = int(sys.stdin.readline())
    for _ in range(K):
        V, E = map(int, sys.stdin.readline().split())
        arr = [[] for _ in range(V)]
        check = [0 for _ in range(V)]
        for _ in range(E):
            u, v = map(int, sys.stdin.readline().split())
            arr[u-1].append(v-1)
            arr[v-1].append(u-1)

        ret = 0
        for i in range(V):
            if not check[i]:
                ret = BFS(i, check, arr)
                if ret == 1:
                    break
        if ret == 0: print("YES")
        else: print("NO")
solution()

https://www.acmicpc.net/problem/1707