[백준] 1707 파이썬(python) : 이분 그래프

https://www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

 

 

from collections import deque
import sys
sys.setrecursionlimit(10**6)
k = int(sys.stdin.readline())

def dfs(start, group):
    visit[start] = group

    for i in graph[start]:
        if not visit[i]:
            a = dfs(i, -group)
            if not a:
                return False
        elif visit[i] == visit[start]:
            return False
    return True

for _ in range(k):
    v, e = map(int, sys.stdin.readline().split())
    graph = [ [] for _ in range(v+1) ]
    visit = [0] * (v+1)
    for _ in range(e):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)
    for i in range(1, v+1):
        if not visit[i]:
            result = dfs(i, 1)
            if not result:
                break
    print("YES" if result else "NO")