백준 1707 파이썬 - 이분 그래프

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

1707번: 이분 그래프

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

코드

from collections import deque
import sys
k = int(sys.stdin.readline())
def bfs(start):
    bi[start] = 1
    q = deque()
    q.append(start)
    while q:
        a = q.popleft()
        for i in s[a]:
            if bi[i] == 0:
                bi[i] = -bi[a]
                q.append(i)
            else:
                if bi[i] == bi[a]:
                    return False
    return True
for i in range(k):
    v, e = map(int, sys.stdin.readline().split())
    isTrue = True
    s = [[] for _ in range(v + 1)]
    bi = [0 for _ in range(v + 1)]
    for j in range(e):
        a, b = map(int, sys.stdin.readline().split())
        s[a].append(b)
        s[b].append(a)
    for y in range(1, v + 1):
        if bi[y] == 0:
            if not bfs(y):
                isTrue = False
                break
    print("YES" if isTrue else "NO")

코드

이분그래프란 인접한 정점들은 서로 다른 두 색 중 무조건 다른 색으로 칠할 수 있는 그래프이다.

 

맨처음 노드에 1을 넣고 다음 탐색하는 노드에 -1을 곱한 값을 계속 대응시키는 배열에 넣고 탐색하다가 다음 이동할 노드에 현재 노드의 값(1 or -1)이 같으면 이분 가능하지 않다는 뜻이므로 탐색을 정지하고 NO를 출력한다.