[BOJ] 1707번: 이분 그래프

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

주어진 그래프가 이분그래프인지 판단하기 위해서는

i) 주어진 그래프들을 Connected component 단위로 분해한다.

ii) 각 CC 단위에서 한 점을 기준으로 떨어진 거리를 기록한다.

iii) 각 edge에 대해서, 그 edge의 vertex 2개를 A, B라고 하고 기준점을 O라고 할 때 O에서 A까지 이르는 거리와 O에서 B까지 이르는 거리가 같은 경우가 하나라도 있으면 이 그래프는 이분그래프가 아니다. 그렇지 않고 모든 인접한 두 점 간에 이르는 거리가 1 차이 난다면 이 그래프는 이분그래프이다.

이 세가지 과정을 거치면 됩니다. 이에 대한 증명은 어떤 그래프가 이분그래프이면 같은 집합내에 속한 정점끼리의 거리가 무조건 짝수이다가 필요충분임을 보임으로서 해결됩니다.

https://github.com/encrypted-def/BOJ/blob/master/1707.cpp