[백준] 1707 이분 그래프

---

주어진 그래프를 이분 그래프인지 판별하는 문제이다.

 

가장 중요한 점은 이분 그래프를 판별하는 알고리즘이다. 처음에는 사이클이 생길 경우 반드시 이분 그래프가 될 수 없다고 생각하였다. 하지만 4개의 정점이 사각형 형태의 그래프를 형성할 경우를 가정해보면, 사이클이 생겨도 이분그래프가 될 수 있다.

 

결국 문제를 해결하지 못해 풀이를 찾아보았다. 대표적인 풀이는 노드마다 색을 칠하는 것이다. DFS, BFS 모두 가능하며 방문한 노드의 인접한 노드중 이미 방문한 노드의 색이 현재 노드의 색과 동일할 경우 이분 그래프가 될 수 없다.

 

여기서 유의 해야할 점은 모든 그래프가 연결 그래프라는 보장이 없다는 것이다. 그리고 비연결 그래프라고 할 지라도 이분 그래프라는 보장이 없기 때문에 모든 노드를 방문하여 색을 칠해야 한다.

from sys import stdin
from collections import deque

readline = stdin.readline


def is_bipartition():
    V, E = map(int, readline().split())
    graph = [[] for _ in range(V+1)]
    visited  = [False] * (V+1)
    
    for _ in range(E):
        u, v = map(int, readline().split())
        graph[u].append(v)
        graph[v].append(u)

    # 연결, 비연결 그래프 모두 고려
    # 모든 노드를 방문해야한다.
    for i in range(1, V+1):
        if not visited[i]:
            ans = bfs(graph, visited, i)
            if not ans:
                return False

    return True

def bfs(graph, visited, start):
    q = deque()
    q.append(start)
    # 노드에 색을 칠함
    black = [False for _ in range(len(graph))]
    
    black[start] = True
    visited[start] = True

    while q:
        u = q.popleft()
    
        for adj in graph[u]:
            if not visited[adj]:
                q.append(adj)
                # 방문하지 않은 노드의 경우
                # 부모 노드와 다른 색을 칠한다.
                black[adj] = not black[u]
                visited[adj] = True
                continue
            # 만약 인접한 노드중 이미 방문한 노드가
            # 현재 노드와 색이 같을 경우
            # 이분 그래프가 될 수 없다.
            if visited[adj] and black[u] == black[adj]:
                return False

    return True


if __name__ == "__main__":
    K = int(readline().strip())
    for _ in range(K):
        if is_bipartition():
            print("YES")
        else:
            print("NO")