BOJ 1707 이분 그래프

이분그래프

난이도 : MH

이분 그래프란?

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

-> 인접하고 있는 노드가 서로 다른 2개의 색을 칠하는 것이 가능한 그래프

DFS나 BFS 로 노드를 따라가면서 1이나 -1로 색을 칠한다.

이 때, 인접한 노드의 색이 자신과 같은 색으로 이미 칠해져 있다면, 이분 그래프가 아닌 것을 확인할 수 있음

그런데 인풋 맵 안에 partial graph가 존재할 수 있으므로,

반복문을 통해 모든 노드를 확인해야 함