코드

    
import sys

input = sys.stdin.readline
T = int(input())

for _ in range(T):
    V,E = map(int,input().split(" "))

    edges = [list(map(int, input().split(" "))) for _ in range(E)]
    graph = [[] for _ in range(V+1)]

    for e in edges:
        a,b = e
        graph[a].append(b)
        graph[b].append(a)


    from collections import deque


    colors = [-1 for _ in range(V+1)]

    def bfs(x,color):
        Q = deque([x])
        visited[x] = color

        while Q:
            x = Q.popleft()
            color = visited[x]

            for num in graph[x]:
                if visited[num] == color:
                    return False
                
                if visited[num] == 0:
                    visited[num] = -color
                    Q.append(num)


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

풀이

• 인접하는 정점이 다른 집합이면 되는 이분 그래프이다. (같은 집합의 정점은 이어져있지 않아야 한다)
• 특정 정점과 인접한 정점은 다른 색으로 칠해지면 된다.
• 코드화 하기 위해 color와 -color로 색을 바꿔줫다.