[백준] 1707 이분 그래프 python

www.acmicpc.net/problem/1707

1707번: 이분 그래프

import sys
input = sys.stdin.readline
from collections import deque

K = int(input())
for tc in range(K):
    V, E = map(int, input().split())
    # 인접 리스트 
    link_arr = [list() for _ in range(V + 1)]
    for _ in range(E):
        n1, n2 = map(int, input().split())
        link_arr[n1].append(n2)
        link_arr[n2].append(n1)
    # 방문 확인
    visit = [0] * (V + 1)

    def bfs(start):
        q = deque()
        q.append(start)
        visit[start] = 1
        while q:
            cur = q.popleft()
            for i in range(len(link_arr[cur])):
                adj = link_arr[cur][i]
                if visit[adj]:
                    if (visit[cur] == 2 and visit[adj] == 2) or (visit[cur] == 1 and visit[adj] == 1):
                        return False
                    else:
                        continue
                if visit[cur] % 2 : # 홀수인경우
                    visit[adj] = 2
                else:
                    visit[adj] = 1
                q.append(adj)
        return True
    result = True
    for i in range(1, V + 1):
        if visit[i]: continue
        result = bfs(i)
        if not result:
            break

    print("YES" if result else "NO")

bfs 변형 문제이다

방문할때 방문하지 않았던 점이면 현재 정점과 다른 숫자를 채운다(현재 정점이 1이면 인접한 점은 2로. 현재 정점이 2이면 1로)

방문한 정점에 대해서 인접정점을 확인하면서 같은 숫자가 아닌경우 continue로 넘어가고, 같은 경우 bfs를 끝내고 False를 반환한다.

반복문을 통해 모든 정점에 대해서 bfs를 돌리는데 하나라도 False가 나오면 NO를 출력하고 모든 점이 True이면 YES를 출력한다.