[백준] 1707번:이분 그래프 (python 파이썬)

문제

www.acmicpc.net/problem/1707

1707번: 이분 그래프

 

풀이

처음엔 배열을 이용해 dfs를 사용하려 했는데, 메모리초과가 났다 ㅠㅠ

1과 2가 연결되어 있으면 arr[1][2] = arr[2][1] = 1 이런식으로 했더니 . . !

방법을 바꿔서 bfs로 deque를 사용하여 해결했다.

 

이분그래프란, 간단히 말하면 인접한 정점끼리 다른 색으로 칠할 수 있는 그래프이다.

이를 visited 배열을 통해 방문하지 않았으면 0으로, 방문하였으면 -1과 1로 구분해주었다.

 

 

소스코드

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

def bfs(x):
    visited[x]=1
    q = deque()
    q.append(x)
    while q:
        a = q.popleft()
        for i in que[a]:
            if visited[i]==0:
                visited[i] = -visited[a]
                q.append(i)
            else:
                if visited[i] == visited[a]:
                    return False
    return True


k = int(input())
for i in range(k):
    v, e = map(int, input().split())
    que = [[] for i in range(v+1)]
    visited = [0]*(v+1)
    flg = 1
    for j in range(e):
        a, b = map(int, input().split())
        que[a].append(b)
        que[b].append(a)
    for k in range(1, v+1):
        if visited[k]==0:
            if not bfs(k):
                flg = -1
                break
    print('YES' if flg==1 else 'NO')