BOJ 1707:: 이분 그래프

http://acmicpc.net/problem/1707

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력으로 주어지는 그래프는 단순 그래프이다.

…라는데 그냥 변으로 이어진 꼭짓점끼리 다른 색으로 칠해서 모든 꼭짓점을 두 색으로만 칠할 수 있는지 판정하면 됩니다. 왜 이게 같은 말인지는 생각해보면 금방 나옵니다.

그래프가 좀 많이 이상하긴 한데 그냥 봅시다. 일단 위 그래프는 이분 그래프가 맞습니다.

근데 이런 그래프는 절대 색 두 개만 가지고는 색칠할 수 없습니다. 그래서 이걸 어떻게 판정하냐? 그래프 그린 모양을 보면 알겠지만 BFS를 쓰면 됩니다. (꼭 정답이 이것만 있는 건 아니고, DFS도 충분히 가능합니다.)

이분 그래프는 BFS를 할 때 같은 레벨의 꼭짓점끼리는 무조건 같은 색으로 칠해집니다. 그래서 어떤 꼭짓점에서 시작해 BFS로 꼭짓점을 방문하다가 만약 한 레벨 안에서 꼭짓점을 다른 색으로 칠해야 하는 일이 있으면 무조건 이분 그래프가 아닌 것이고, 모든 꼭짓점을 다 방문했는데도 그런 일이 없으면 이분 그래프인 것이죠. 단, 그래프가 연결 그래프가 아니면 BFS로 모든 꼭짓점을 방문할 수 없으므로 일단 한 꼭짓점과 그와 연결된 꼭짓점을 방문한 후 남은 꼭짓점이 있으면 계속 BFS를 돌립니다. 연결 요소 계산하는 방식이랑 똑같이.