BFS, 이분 그래프 - 1707번: 이분 그래프

1. BFS + 색칠: 인접한 노드를 0과 1로 번갈아 색칠하며 탐색
2. 충돌 검사: 같은 색의 노드가 인접하면 즉시 False 반환
3. 중복 방지: 큐에 넣을 때 바로 colors[c] 설정하여 중복 삽입 차단
4. 연결 요소 처리: 1~V까지 순회하며 끊어진 그래프도 모두 검사
5. 시간복잡도: O(V + E)로 최적화

from collections import defaultdict, deque
import sys

input = sys.stdin.readline

K = int(input())


def bfs():

    # 방문 체크와 색상 관리를 동시에 처리 가능(-1: 방문 안한 노드, 0/1: 색상)
    colors = [-1] * (V + 1)

    # 그래프의 전체 노드 순회해야 끊어진 그래프도 커버 가능함
    for i in range(1, V + 1):
        if colors[i] != -1:
            continue

        q = deque()

        q.append((i, 0))
        colors[i] = 0

        while q:
            node, color = q.popleft()

            other_color = -1
            if color == 0:
                other_color = 1
            else:
                other_color = 0

            for c in graph[node]:
                # 자식 노드가 부모 노드의 색상이 일치한다면 이분 그래프가 아니므로 False 리턴
                if colors[c] == color:
                    return False

                # 아직 방문 안한 자식 노드의 경우
                if colors[c] == -1:
                    q.append((c, other_color))
                    colors[c] = other_color

    return True


for test in range(K):
    V, E = map(int, input().split())

    graph = defaultdict(list)

    for e in range(E):
        u, v = map(int, input().split())

        graph[u].append(v)
        graph[v].append(u)

    if bfs():
        print("YES")
    else:
        print("NO")