[백준] 1707 이분 그래프, python

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

 

 

 

 

이분 그래프(bipartite graph), python

이분 그래프(bipartite graph), python

 

 

 

예제 입력에서 첫번째 케이스의 경우 모든 정점을 색칠할 수 있다. 따라서 이분 그래프이다.

 

 

 

 

 

 

 

 

예제 입력의 두번째 케이스는 3번과 4번 정점이 같은색으로 칠해진다. 이분 그래프가 아니다.

 

 

 

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

k = int(input())

def valid(graph):
    # 색을 칠했다면 그 정점을 방문한것이므로 방문체크도 같이 할 수 있다.
    color = {}

    for start in graph:
        if start not in color:
            q = deque([start])
            # 처음 색을 칠해준다(색: 0)
            color[start] = 0

            while q:
                cur = q.popleft()

                for next in graph[cur]:
                    # 인접한 정점의 색을 아직 칠하지 않았다면
                    if next not in color:
                        # 색을 반대색(0이면 1, 1이면 0)으로 칠해준다.
                        color[next] = 1-color[cur]
                        q.append(next)
                    # 인접한 정점의 색이 같다면 이분 그래프가 아니다.
                    elif color[next] == color[cur]:
                        return False

    # 모든 정점을 전부 칠했다면 이분 그래프이다.                    
    return True


for _ in range(k):
    v,e = map(int, input().split())
    graph = defaultdict(list)

    for _ in range(e):
        u,v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    print('YES' if valid(graph) else 'NO')