백준 - 그래프(# 1707)

이분 그래프

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

Code

import sys

def bfs(v, visited, color):
    queue = [v]
    visited[v] = True
    color[v] = 1
    while queue:
        s = queue.pop(0)
        for nxt in adj_list[s]:
            if not visited[nxt]:
                queue.append(nxt)
                color[nxt] = color[s] * (-1)
                visited[nxt] = True
            else:
                if color[s] == color[nxt]:
                    return False
    return True

t = int(input())
for _ in range(t):
    v, e = map(int, sys.stdin.readline().split())
    adj_list = [[] for _ in range(v+1)]
    for _ in range(e):
        a, b = map(int, sys.stdin.readline().split())
        adj_list[a].append(b)
        adj_list[b].append(a)

    visited = [False for _ in range(v+1)]
    color = [0 for _ in range(v+1)]
    result = True

    for s in range(1,v+1):
        if not visited[s]:
            if not bfs(s, visited, color):
                result = False
                break

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