1707: 이분 그래프

• 이분 그래프를 판별하기 위해서, depth마다 color 값을 1과 -1로 번갈아가면서 할당해줌
  -> 만약 이전 depth의 node와 현재 depth의 node가 같은 color라면, print("NO")
• 처음에 Recursion error가 발생해서 "sys.setrecursionlimit(1000000)"를 추가해줌
• 메모리 초과가 발생했는데, 이는 pypy3 말고 python3로 제출하니까 해결됨
• 모든 노드들을 순회하면서 color가 번갈아가면서 할당되는 지 확인해주어야함
  -> for문을 돌 때, visit[x] == 0인 경우만 dfs순회를 하면 시간을 단축할 수 있음

import sys
sys.setrecursionlimit(1000000)

def dfs(start, color):
        global flag
        visit[start] = color
        for i in range(len(adjacent[start])):
            if visit[adjacent[start][i]] == 0:
                dfs(adjacent[start][i], -color) # depth마다 color 값을 1과 -1로 번갈아가면서 할당
                if visit[start] == visit[adjacent[start][i]]:
                    flag = 1
                    return
            elif visit[start] == visit[adjacent[start][i]]:
                flag = 1
                return

K = int(input())
for k in range(K):
    tmp = list(map(int, sys.stdin.readline()[:-1].split(' ')))
    N = tmp[0]; M = tmp[1]
    adjacent = [[] for _ in range(N+1)]
    for _ in range(M):
        t0, t1 = map(int, sys.stdin.readline()[:-1].split(' '))
        adjacent[t0].append(t1)
        adjacent[t1].append(t0)

    flag = 0
    visit = [0] * (N+1)
    for x in range(1, N+1):
        if visit[x] == 0:
            dfs(x, 1)

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