[백준] 1707번 - 이분 그래프 (파이썬)

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

# 이분 그래프
import sys
from collections import deque
input = sys.stdin.readline


def bfs(start):
    global result
    q = deque()
    q.append(start)
    visited[start] = 0
    while q:
        node = q.popleft()
        for nnode in arr[node]:
            if visited[nnode] == -1:
                visited[nnode] = visited[node] % 2 + 1
                q.append(nnode)
            else:
                if visited[nnode] == visited[node]:
                    result = 'NO'
                    return


T = int(input())
for _ in range(T):
    V, E = map(int, input().split())
    visited = [-1] * (V+1)
    arr = [[] for _ in range(V+1)]
    for _ in range(E):
        a, b = map(int, input().split())
        arr[a].append(b)
        arr[b].append(a)

    result = 'YES'
    for i in range(1, len(visited)):
        if visited[i] == -1 and result == 'YES':
            bfs(i)
    print(result)

 

BFS

1. 인접리스트로 입력을 받는다

2. 노드 마다 방문하지 않았고 result가 YES이면 (그래프가 연결이 다 안됐을 가능성이 있어서)

  - q가 빌 때 까지

     - 현재 방문 값 % 2 + 1 (0 이면 1 , 1이면 0)을 연결된 다음 노드의 방문 값에 넣어준다.

     - 이후 q에 append

3. result 출력

 

두가지 색상으로 모든 노드를 칠 할 수 있을 경우 이분그래프가 성립이 된다