풀이

처음 본 이 문제는 나에게 매우 까다로운 문제였다. 풀이 방법은 bfs로 돌면서 본인과 연결되어 있는 노드에 대해서 다른 그룹으로 지정해주고, 돌다가 본인과 연결되어 있는데 같은 그룹으로 속해있으면 False를 반환해주면 된다.

from collections import deque
import sys
k = int(input())
for test_case in range(k):
    V, E = map(int, sys.stdin.readline().split())

    lst = [[] for _ in range(V+1)]
    for i in range(E):
        u, v = map(int, sys.stdin.readline().split())
        lst[u].append(v)
        lst[v].append(u)

    visited = [False] * (V+1)
    grp = [0] * (V+1)
    result = True
    def bfs(start):
        global result
        q = deque()
        q.append(start)
        visited[start] = True
        while q:
            current = q.popleft()
            for k in lst[current]:
                if not visited[k]:
                    visited[k] = True
                    grp[k] = 3-grp[current]
                    q.append(k)
                else:
                    if grp[current] == grp[k]:
                        result = False
                        return

    for i in range(1, V+1):
        bfs(i)
        if result == False:
            break

    if result == False:
        print('NO')
    else: print('YES')