[1707] 이분 그래프

이분 그래프는 두가지 색으로 그래프를 칠했을때

인접한 노드끼리는 다른 색상으로 칠해지는 그래프다.

 

그래서 실제로 빨강과 검정으로 칠해보고

같은 색상으로 칠할수밖에 없는 경우가 생기면 NO를 return한다.

 

혹시 간선없이 고립된 노드가 있을 경우를 체크했는데,

for문을 1번부터 V번까지 돌기 때문에 고립된 노드도 칠해지기 때문에 불필요한 엣지케이스 체크였다.

'''
1707 - 이분 그래프
'''

import sys
from collections import deque

def coloring(V, graph):
    node_color = [None for _ in range(V+1)]

    for v in range(1, V+1):
        if node_color[v] is None:
            stack = deque()
            stack.append([v, "black"])
            node_color[v] = "black"
            while stack:
                # print(node_color)
                node, color = stack.pop()
                next_color = None
                if color == "black":
                    next_color = "red"
                elif color == "red":
                    next_color = "black"
                for next_node in graph[node]:
                    if color == node_color[next_node]:
                        return "NO"
                    if node_color[next_node] is None:
                        stack.append([next_node, next_color])
                        node_color[next_node] = next_color

    if None in set(node_color[1:]):
        return "NO"

    return "YES"

T = int(sys.stdin.readline().strip())
for testcase in range(1, T + 1):
    V, E = map(int, sys.stdin.readline().split())
    lines = [list(map(int, sys.stdin.readline().split())) for _ in range(E)]

    graph = {i: [] for i in range(1, V + 1)}
    for u, v in lines:
        graph[u].append(v)
        graph[v].append(u)

    result = coloring(V, graph)
    print(f"{result}")