[백준] 1707 이분 그래프

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

작업에 제시된 두 부분으로 구성된 그래프에 대한 설명은 이해하기 쉽게 다음 블로그에 설명되어 있습니다.

https://hongcoding.tistory.com/20

저도 위 블로그에서 힌트를 얻어 코드를 완성하고 그 결과를 공유합니다.

from sys import stdin
from collections import deque


def bfs(n):
    visited(n) = 1  # 처음 방문한 노드의 색상을 1로 지정, 이웃한 노드의 색상은 -1로 지정한다.


    q = deque(())
    q.append(n)
    while q:
        n = q.popleft()
        for c in g(n):      # 현재 방문한 노드의 이웃한 노드들에 대해 조사한다.


            if not visited(c):  # 새롭게 방문한 노드에 방문한적 없을 경우
                q.append(c)     # 이 노드의 이웃을 방문하기 위해 노드 번호를 큐에 추가한다.


                visited(c) = -visited(n)    # 이 노드는 그전 노드와 다른 색을 가진다
            else:               # 이미 방문했던 노드일 때
                if visited(c) == visited(n): # 이 노드는 이미 색상이 지정되어 있지만 직전 노드와 색상이 같을 경우
                    return False    # 이분 그래프를 만족하지 못하므로 False를 반환한다.


    return True


for i in range(int(input())):
    n, m = map(int, input().split())
    g = (() for _ in range(n+1))
    visited = (0) * (n+1)   # 방문하지 않은 노드를 0으로 표시
    visited(0) = 1

    for j in range(m):
        a, b = map(int, stdin.readline().split())
        g(a).append(b)
        g(b).append(a)

    ans="YES"
    # 연결 그래프일 경우 한번만 수행하면 되지만, 비연결 그래프일 경우 한번에
    # 모든 노드를 방문할 수 없으므로 리스트에 0이 없어질 때 까지 반복한다.


    while 0 in visited:
        v = visited.index(0)    # 방문하지 않은 노드에 bfs 수행
        if not bfs(v):
            ans="NO"
            break

    print(ans)