백준 1707번 이분 그래프

문제 풀이

• 이분 그래프가 아닌 조건:
  사이클이 발생했을 때, 사이클에 속한 노드 개수가 홀수

예시 1

아래와 같은 그래프가 존재한다고 할 때 2, 3, 4 노드가 사이클을 이루고, 노드의 개수는 홀수입니다.

 1
 |
 2---
 |	|
 3	|
 |	|
 4---

따라서, 이분 그래프가 아닙니다.

예시 2

아래와 같은 그래프가 존재한다고 할 때 3, 4 노드가 사이클을 이루고, 노드의 개수는 짝수입니다.

 1
 |
 2
 |	
 3---	
 |	|
 4---

따라서, 이분 그래프입니다.

코드 풀이

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


def bfs(start):
    q = deque()
    q.append(start)
    visited[start] = 1
    while q:
        x = q.popleft()
        for i in graph[x]:
            if not visited[i]:
                q.append(i)
                visited[i] = -1 * visited[x]   # 부모 노드와 다른 상태를 가지도록
            elif visited[i] == visited[x]:   # 부모 노드의 상태와 같다면 홀수 개의 노드로 이루어진 사이클이 존재한다는 의미: 이분 그래프 X
                return False

    return True


K = int(input())

for _ in range(K):
    V, E = map(int, input().split())
    graph = [[] for _ in range(V+1)]
    visited = [0] * (V+1)
    for _ in range(E):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    for i in range(1, V+1):   # 모든 노드를 시작점으로 BFS 시행
        if not visited[i]:
            result = bfs(i)   # 이분 그래프: True, 아닐 시: False
            if not result:   # 이분 그래프가 아닌 즉시 반복 종료.
                break

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