1707번 - 이분 그래프
메모리 초과는 제 경우에 간선의 정보를 인접 행렬(2차원배열)로 저장했고
인접 리스트(VECTOR)로 수정한 뒤에 해결됐습니다.
반례이전에 다른분이 올려주신 자주 틀리는 경우도 꼭 챙겨보시고 돌려보세요 화이팅
반례모음16 61 33 44 22 55 66 1YES23 31 22 31 32 11 2NO YES15 41 22 33 14 5NO14 21 23 4YES15 41 23 44 53 5NO14 31 44 33 2YES15 41 21 32 43 5YES14 31 24 32 3YES
감사합니다.
덕분에 반례 찾았습니다! 감사합니다~!
감사합니다 반례 발견했습니다!
감사합니다!!!!!!!!!
덕분에 많은 시간 아꼈습니다!
감사합니다!!
덕분에 실수 2개나 찾았습니다...
14 21 23 4YES
이게 왜 yes가되나요?
mjmd58님께) S1={1,3}, S2={2,4 이렇게 분할하면 각 집단 내에서 인접관계가 없게 됩니다. 이분 그래프는 연결된 점들이 서로 다른 색을 가지게 해서 두 가지 색으로 그릴 수 있냐는 문제입니다!
댓글을 작성하려면 로그인해야 합니다.
ohdo123 2년 전 21
메모리 초과는 제 경우에 간선의 정보를 인접 행렬(2차원배열)로 저장했고
인접 리스트(VECTOR)로 수정한 뒤에 해결됐습니다.
반례이전에 다른분이 올려주신 자주 틀리는 경우도 꼭 챙겨보시고 돌려보세요 화이팅
반례모음
1
6 6
1 3
3 4
4 2
2 5
5 6
6 1
YES
2
3 3
1 2
2 3
1 3
2 1
1 2
NO YES
1
5 4
1 2
2 3
3 1
4 5
NO
1
4 2
1 2
3 4
YES
1
5 4
1 2
3 4
4 5
3 5
NO
1
4 3
1 4
4 3
3 2
YES
1
5 4
1 2
1 3
2 4
3 5
YES
1
4 3
1 2
4 3
2 3
YES