백준 온라인 저지, BFS / 1707번: 이분그래프 (파이썬 / , 백준 골드문제)

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고 주어진다. 

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

제한

• 2 ≤ K ≤ 5
• 1 ≤ V ≤ 20,000
• 1 ≤ E ≤ 200,000

예제 입력 1

2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2

예제 출력 1

YES
NO

힌트

접근 방법

- BFS를 통해 한 정점을 1, 다른 정점을 2으로 바꿔가며 이를 갱신하다가 모든 정점을 문제없이 분할할 수 있다면 YES, 아니면 NO를 출력한다.

코드

# https://www.acmicpc.net/problem/1707
# 접근 방법
# BFS를 통해 한 정점을 1, 다른 정점을 2으로 바꿔가며 이를 갱신하다가 모든 정점을 문제없이 분할할 수 있다면 YES, 아니면 NO를 출력한다.
from collections import deque
import sys
input = sys.stdin.readline
tc = int(input())
for _ in range(tc):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    for _ in range(e):
        u1, u2 = map(int, input().split())
        graph[u1].append(u2)
        graph[u2].append(u1)
    visited = [0 for _ in range(v+1)]
    is_bipartite_graph = True
    visited_of_nodes = v
    while visited_of_nodes > 0 and is_bipartite_graph:
        
        for i in range(1, v+1):
            if not visited[i]:
                queue = deque([])
                queue.append([i, 1]) # 정점, 번호
                visited[i] = 1
                visited_of_nodes -= 1
                break
            
        while queue and is_bipartite_graph:
            node, num = queue.popleft()
            num = (num % 2 + 1)
            for u in graph[node]:
                if not visited[u]:
                    visited[u] = num
                    queue.append([u, num])
                    visited_of_nodes -= 1
                elif visited[u] != num:
                    is_bipartite_graph = False
                    break

    if is_bipartite_graph:
        print('YES')
    else:
        print('NO')