[파이썬] [BFS] 백준 1707 이분 그래프

문제

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

1707번: 이분 그래프

코드

import sys
from collections import deque
input=sys.stdin.readline
    
t=int(input())
for _ in range(t):
    v,e=map(int,input().split())
    
    visited=[0]*(v+1)
    graph=[[] for _ in range(v+1)]
    
    for _ in range(e):
        a,b=map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    
    queue=deque()
    group=1
    result=True
    for i in range(1,v+1):
        if visited[i]==0:
            queue.append(i)
            visited[i]=group
            while queue:
                p=queue.popleft()
                for j in graph[p]:
                    if visited[j]==0:
                        queue.append(j)
                        visited[j]=-1*visited[p]
                    else:
                        if visited[j]==visited[p]:
                            result=False
    if result:
        print("YES")
    else:
        print("NO")

이분 그래프(Bipartite Graph)란

인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프