[Algorithm|Python] 백준 2776번 / 99클럽 코테 스터디 9일차 TIL

import sys
from collections import deque

input = sys.stdin.readline

def BFS(start, group):
    que = deque([start])
    visited[start] = group
    
    while que:
        node = que.popleft()
        
        for linked_node in graph[node]:
            if not visited[linked_node]:
                que.append(linked_node)
                visited[linked_node] = -visited[node]
            elif visited[linked_node] == visited[node]:
                return True
    return False

if __name__ == "__main__":
    K = int(input())
    
    for _ in range(K):
        V, E = map(int, input().split())
        graph = [[] for _ in range(V+1)]
        
        for _ in range(E):
            u, v = map(int, input().split())
            graph[u].append(v)
            graph[v].append(u)
            
        visited = [False] * (V + 1)
        
        for i in range(1, V+1):
            if not visited[i]:
                result = BFS(i, 1)
                if result:
                    print("NO")
                    break
        else:
            print("YES")