nuclear852   3년 전

풀이법은 다음과 같습니다:

먼저 union-find를 통해 connected component를 검색합니다.

해당 connected component의 노드보다 엣지의 갯수가 많으면 -1 출력합니다. (49~72)

그 후에는 무조건적으로 번호가 결정되는 애들을 큐를 이용하여 answer를 정합니다. (74~98)

그 후 짬처리들은 두 개 중에 결정을 해야하는 놈들입니다. 

제가 궁금한 것이 여기에 있습니다.

1) 여기서 이분 매칭을 이용해줘야 합니까?

2) 아니면 그냥 포문 돌려서 적당히 매칭해줘도 됩니까?

2)로 풀었는데 WA를 맞아서 2)의 논리가 잘못된 건지,

아니면 코드 자체에 문제가 있는지, 

그것도 아니라면 반례 하나 주시면 정말 감사드리겠습니다..

nuclear852   3년 전

반례

5

2 1

3 4

3 2

4 1

4 5

nuclear852   3년 전

2) 에 문제가 있는 것을 알게 되어서

하나하나 큐에 어봐서 영향가는 edge들을 결정하는 식으로 바꿨습니다.

반례는 해결되었지만 여전히 에러가 뜹니다. 도움이 필요합니다. ㅠ

nuclear852   3년 전

4

3 1

4 3

4 5

5 3

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