jhlee2718   4달 전

DFS로 인접 노드들 색깔 칠하는 방법으로 했거든요


틀린 구석이 전혀 없어보이는데 계속 틀렸다고 하니 스트레스 받아 죽겠습니다 ㅠㅠ


어느 부분에서 틀렸을까요 ㅠㅠ

yohan5050   4달 전

다른 이유도 있을 수 있겠지만 일단, dfs탐색을 0번 정점에서만 시작해서 그런 것 아닐까요?

주어진 그래프가 서로 연결이 안되어있는 두 덩어리(?)로 나눠져 있는 경우에는 두 덩어리 모두 이분 그래프인지 살펴봐야 하는데,

올려주신 코드에 의하면 아마도 하나의 덩어리만 dfs탐색하고 끝이기 때문에, 나머지 하나의 덩어리가 이분그래프가 아닌 경우에는 

틀리게 됩니다. 예시를 하나 드리자면,

1

5 4

1 2

3 4

3 5

4 5

-> NO가 나와야 합니다.





jhlee2718   4달 전

연결그래프가 아닌 경우를 체크안했습니다!!

감사합니다!!

댓글을 작성하려면 로그인해야 합니다.