13265색칠하기

acmicpc.net/problem/13265

이분그래프 문제같다.

나는 dfs가 좋다.

dfs를 진행하면서, 색을 계속 바꿔가며 (not c)칠한다.

만일 이미 색칠되어있는 칸을 만났는데, 현재색과 같으면 불가능한것이므로 바로 종료한다

아니면 계속dfs를 진행한다

이전에 이분그래프문제를 풀어봤더니 쉽게 풀었다.

import sysfrom collections import dequeinput = sys.stdin.readlinedef bfs(i):
    q = deque()    q.append((i, True))    while q:        now, c = q.popleft()
        for next in arr[now]:            if visited[next] == c:
                return False            elif visited[next] == -1:
                q.append((next, not c))                visited[next] = not c
    return Truet = int(input())for _ in range(t):
    n, m = map(int, input().split())    arr = [[] for _ in range(n + 1)]
    visited = [-1 for _ in range(n + 1)]    for __ in range(m):
        a, b = map(int, input().split())        arr[a].append(b)
        arr[b].append(a)    for i in range(1, n + 1):
        if visited[i] == -1:            visited[i] = True
            tmp = bfs(i)        if not tmp:            break
    print("possible" if tmp else "impossible")