이분 그래프

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

처음에 지문 읽고 이해가 안돼서 (ㅠㅠ) 구글에서 이미지 봤다

자료구조 시간에 배웠던 건데 구현해보는 건 처음이다

그냥 번갈아서 색 칠하고 겹치면 Out 시키면 되는 거 같다

그러면 dfs bfs 중 하나 쓰면 될 듯하다

 

import sys
from collections import deque

input = sys.stdin.readline
tk = int(input())


def bfs(x):
    q = deque()
    q.append(x)
    vis[x] = "W"
    while q:
        cx = q.popleft()
        for nx in g[cx]:
            if vis[nx] == "0":
                q.append(nx)
                vis[nx] = "B" if vis[cx] == "W" else "W"
            elif vis[nx] == vis[cx]:
                return False
    return True


for _ in range(tk):
    v, e = map(int, input().split())
    g = {i: [] for i in range(1, v + 1)}
    vis = {i: "0" for i in range(1, v + 1)}
    for _ in range(e):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
    res = "YES"
    for i in range(1, v + 1):
        if vis[i] == "0":
            if not bfs(i):
                res = "NO"
                break
    print(res)

혹시 연결된 그래프가 아닐 수도 있으니까 1~v+1까지 돌면서 방문 한 했으면 bfs돌린다

만약 bfs 반환값이 false 면 바로 break , print "NO"

배열 인덱스로 노드 찾는 것보다 딕셔너리 쓰는 게 덜 헷갈려서 좋은 것 같다

for 돌 때 items() 해줘야 하는 건 조금 귀찮지만...

 

bfs 내에서 색칠하는 것 때문에 케이스 몇개를 통과를 못 했는데

cx에 색 칠하고 for 로 나오는 nx들에 모두 cx와 다른 색 (그러니까 nx들끼리는 같은 색) 해준 게 문제였다

pop 한 다음에 0, 1 번갈아가면서 W, B 을 칠했었는데 큐에서 꺼내온 노드를 기준으로 바로 색을 바꿔서 인접노드 처리에는 답이 아니었던 것

cx가 흰색이면 검정색 칠하고

검정이면 흰색 반대로 칠하게 해줬다

간단한데 조금 헤맴