1. 문제 설명

이분 그래프

2. 문제 분석

DFS를 통해 이분 그래프를 점검할 수 있다. 재귀적으로 접근했기 때문에 파이썬의 재귀 제한을 풀었고, pypy가 아니라 python3로 제출했다. 전역 변수 플래그를 통해 곧바로 이분 그래프가 아닐 경우를 체크하는 게 핵심.

1. 모든 그래프(연결이 보장되지 않은 무방향 그래프)의 간선을 통해 연결된 노드 두 개를 서로 다른 집합 두 개로 분리할 수 있다.
2. 다른 색의 집합에 넣을 때 그대로 DFS를 실행, 연결된 그래프 중 사이클이 일어났는지 유무를 체크하자. 즉 이미 색이 칠해진 노드에 다른 색이 칠해지는 경우는 이분 그래프가 형성되지 않는다는 뜻이다.
3. 연결되지 않은 노드일 수 있기 때문에 모든 노드에서 연결성을 체크할 수 있도록 DFS를 실행해야 한다.
4. 전역 변수 플래그를 통해 이분 그래프가 아닌 시점을 곧바로 확인할 수 있다.

3. 나의 풀이

import sys
import heapq

sys.setrecursionlimit(10**6)
k = int(sys.stdin.readline().rstrip())
for _ in range(k):
    v, e = map(int, sys.stdin.readline().rstrip().split())
    nodes = [[] for _ in range(v+1)]
    visited = [False for _ in range(v+1)]
    colors = [-1 for _ in range(v+1)]
    for _ in range(e):
        u, v = map(int, sys.stdin.readline().rstrip().split())
        nodes[u].append(v)
        nodes[v].append(u)

    def DFS(node, color):
        global flag
        visited[node] = True
        colors[node] = color

        for next_node in nodes[node]:
            if visited[next_node]:
                if colors[next_node] == color:
                    flag = False
            else:
                DFS(next_node, abs(1-color))

    flag = True
    for i in range(1, v+1):
        if not visited[i]:
            visited[i] = True
            DFS(i, 1)

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