백준 1707 - 이분 그래프

백준 골드 4 이분 그래프 문제이다.

다음과 같은 그래프가 주어지면 해당 그래프가 이분 그래프인지 아닌 지 판별하는 문제이다.

이분 그래프란, 그래프의 정점 집합을 둘로 분할하여, 각 집합에 속한 정점끼리 서로 인접하지 않도록 분할할 수 있는 그래프를 의미한다.

 

이런식..?인데, 파랑끼리 연결 안되고, 빨강끼리 연결 안된 거를 보면 된다.

from collections import deque
def is_bipartite(a, edges):
    color = [0] * (a + 1)
    visited = [False] * (a + 1)
    for v in range(1, a + 1):
        if visited[v]:
            continue
        stack = deque([(v, 1)])
        
        while stack:
            vertex, c = stack.pop()
            
            if visited[vertex]:
                continue
            
            visited[vertex] = True
            color[vertex] = c

            for neighbor in edges[vertex]:
                if not visited[neighbor]:
                    stack.append((neighbor, -c))
                elif color[neighbor] == color[vertex]:
                    return False
    return True

a = int(input())

for _ in range(a):
    b, c = map(int, input().split())    
    edges = [[] for _ in range(b + 1)]
    
    for _ in range(c):
        d, e = map(int, input().split())
        edges[d].append(e)
        edges[e].append(d)
    
    if is_bipartite(b, edges):
        print("YES")
    else:
        print("NO")

스택 큐를 이용해서 DFS로 풀었다.

난 알고리즘이랑 안맞는 것 같다