백준 1707번 이분 그래프 JAVA

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

 

요구사항 정의

• V<=2*10^4
• E<=2*10^5
• 인접한 노드가 같은 집합에 속하는지 여부 체크

 

풀이 방법

그래프 탐색을 수행하면서 인접한 노드가 같은 집합이라면 false를 반환하는 BFS를 구현

사이클이 있는지를 탐색하는 방법과 유사하다

 

처음 틀렸던 이유는 

모든 그래프가 연결되어있다고 생각하고 풀이를 진행해서 틀렸다

다른 사람들도 이 부분에서 실수를 했다는 리뷰가 있는데 문제에 명시했다면 안 틀렸을 수도..

 

시간복잡도는

테스트 케이스 * 노드의 최대 개수이므로

O(5*2*10^4) = O(10^5)

 

코드