[BOJ] 15511번: League of Overwatch at Moloco

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

주어진 그래프를 이분그래프로 분할할 수 있는지를 묻고 있습니다. 그룹을 A, B라고 할 때 아직 그룹에 편입시키지 못한 임의의 노드에 대해 아래와 같은 작업을 반복합니다.

1) 택한 노드를 A에 편입

2) 그 노드로부터 BFS(혹은 DFS)를 돌면서 노드를 택함

3-1) 택한 노드가 이미 그룹에 편입되어있고, 부모 노드와 같은 그룹에 편입된 경우 불가능

3-2) 택한 노드가 이미 그룹에 편입되어있고, 부모 노드와 다른 그룹에 편입된 경우 일단 계속 진행

3-3) 택한 노드가 그룹에 편입되어있지 않을 경우 부모 노드와 다른 그룹에 편입시킴

이것을 그룹에 편입시키지 못한 노드가 없을 때 까지 반복합니다. 정상적으로 종료될 경우 주어진 그래프는 이분그래프로 분할 가능합니다.

https://github.com/blisstoner/BOJ/blob/master/15511.cpp