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

문제:www.acmicpc.net/problem/1707

1707번: 이분 그래프

이 문제는 처음에 문제 자체를 이해 못한 것이 컸다. 문제를 이해해도 어떻게 풀어야 할 지 막막해서 결국 다른 분들의 코드를 참조했다.

from collections import deque
import sys
input = sys.stdin.readline
k = int(input())
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, input().split())
    isTrue = True
    s = [[] for i in range(v + 1)]
    bi = [0 for i in range(v + 1)]
    for j in range(e):
        a, b = map(int, input().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")
​

참조:https://pacific-ocean.tistory.com/349

[백준] 1707번(python 파이썬)

위의 그림들은 문제에 있는 예시로 표현하였다. 첫 번째 예시 같은 경우에는 각 정점마다 같은 값을 가진 정점이 없으므로 "YES"를 출력할 수 있지만 두번 째 예시의 경우에는 3번째 정점에서 4번째 정점과 같은 값을 가져서 False를 발생시키고 "NO"를 출력한다.

이렇게 각 점을 방문하여 확인하면 이분 그래프를 만들 수 있다.