백준: 1707 이분 그래프

문제

1707번: 이분 그래프

 

문제 풀이

 그래프의 연결 정보가 주어질 때, 이분 그래프인지 판단하여 이분 그래프읜 경우 'YES' 아닌 경우는 'NO'를 반환하는 문제이다. 문제를 풀기 위해 이분 그래프에 대한 이해가 필요하다. 이분 그래프를 만족하기 위해서는 2가지 조건이 필요하다. 첫 번째로 한 정점에서 다른 정점으로 연결된 경우, 서로 다른 그룹이어야 한다. 두 번째, 모든 그룹은 2개로 나뉘어야 한다는 조건이 있다.

 문제의 예제 입력 1은 테스트 케이스가 1, 2로 나뉘는데 각 테스트 케이스는 위의 그림과 같다. 테스트 케이스 1은 연결된 정점들을 서로 다른 그룹(색깔)로 구분할 수 있어 이분 그래프의 조건을 만족하지만, 테스트 케이스 2는 빨간색 간선으로 인해 이분 그래프의 조건을 만족하지 못하는 것을 알 수 있다. 따라서 BFS를 통해 순회하면서 현재 정점에서 다른 정점으로 갈 경우, 그룹으로 분류되었다면 해당 그룹과 다른지 판단하여야 한다.

 

코드

from sys import stdin
from collections import deque


def bfs(start):
    q = deque([start])

    while q:
        cur_node = q.popleft()

        for next_node in graph[cur_node]:
            if not check[next_node]:
                check[next_node] = -check[cur_node]
                q.append(next_node)
            elif check[cur_node] == check[next_node]:
                return False
    return True


if __name__ == "__main__":
    tc = int(stdin.readline())

    for _ in range(tc):
        v, e = map(int, stdin.readline().split())
        graph = [[] for _ in range(v)]
        check = [0] * v
        answer = False

        for _ in range(e):
            a, b = map(int, stdin.readline().split())
            a, b = a - 1, b - 1
            graph[a].append(b)
            graph[b].append(a)

        for i in range(v):
            if not check[i]:
                check[i] = 1
                if not bfs(i):
                    break
        else:
            answer = True

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