백준 1707 이분그래프 - 파이썬

문제.

풀이.

이분 그래프는 연결된 정점마다 색을 칠한다고 하면 연결된 정점 끼리의 색이 서로 달라야한다.

즉 예를 들어 (1,3), (2,3) 이 연결되어 있다면 1은 빨간색 3은 파랑색 2는 빨간색 이런식으로 연결된 정점끼리의 색이 달라야한다.

 

풀이.

from collections import deque

def bfs(n):
    visited[n] = 1;
    queue=deque()
    queue.append(n)
    while queue:
        x = queue.popleft()
        for i in matrix[x]:
            if visited[i] == 0:
                visited[i] = -visited[x]
                queue.append(i)
            else:
                if visited[i] == visited[x]:
                    return False
    return True



tc = int(sys.stdin.readline())

for i in range(tc):
    v, e = map(int, sys.stdin.readline().split())
    x, y = [], []
    visited = [0] * (v+1)
    matrix = [[] for r in range(v+1)]
    for j in range(e):
        x, y = map(int, sys.stdin.readline().split())
        matrix[x].append(y)
        matrix[y].append(x)

    result = 'YES'
    for j in range(1, v+1):
        if visited[j] == 0:
            if not bfs(j):
                result = 'NO'
                break
    print(result)