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

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

1707번: 이분 그래프

1. 맨 처음 bfs에 입력한 값은 1로 체크한다

2. 그 다음에 이동할 수 있는 지점은 현재 체크한 값에 -1을 곱하면서 이분한다

3. 만일 다음에 이동할 지점의 체크값과 현재 체크값이 같으면 이분할 수 없다는 뜻이므로 NO를 출력

from collections import deque

def bfs(x):
    q.append(x)
    c[x] = 1
    while q:
        x = q.popleft()
        for nx in a[x]:
            if c[nx] == 0:
                c[nx] = -1*c[x]
                q.append(nx)
            elif c[nx] == c[x]:
                return 1
    return 0

tc = int(input())
while tc:
    v, e = map(int, input().split())
    a = [[] for _ in range(v)]
    c = [0 for _ in range(v)]
    q = deque()
    for _ in range(e):
        x, y = map(int, input().split())
        a[x-1].append(y-1)
        a[y-1].append(x-1)
    ans = 0
    for i in range(v):
        if c[i] == 0:
            ans = bfs(i)
            if ans == 1:
                break
    if ans == 0:
        print("YES")
    else:
        print("NO")
    tc -= 1