3 1 2 -1 -1

3이 없기 때문에 -1을 출력하는게 맞지 않나요?..

술취한 상태에서 글을 너무 험하게 쓴것같아 죄송합니다!..

shiftpsh님 얘기처럼 혹시 n명의 사람중에 포함되지 않는 사람이 있어도 되는 건가 싶어서 코드를 수정했는데도 17퍼에서 틀리네요...ㅋㅋㅋ

조건을 잘 읽어보시면, "모든 사람은 A팀 또는 B팀 중 오직 하나의 팀에 반드시 속해야 한다"고 되어 있습니다. 3 1 2 -1 -1의 경우에는 3이 등장하진 않았지만 어딘가에 배치해주긴 해야 합니다.

반례 더 드리겠습니다.

5
-1 -1

7
1 2
1 3
1 4
2 3
2 4
5 6
6 7
5 7
-1 -1

반례 감사합니다.

그런데 의문이 있는게, 두번째 조건에서 분명 '같은 그룹의 학생들끼리는 모두 서로 아는 사이어야 한다.'라고 되어있을 때,

주신 반례에서 학생이 다섯명인데 다섯명중 한명이라도 서로 모르는 사이이면 A그룹 B그룹 어느 곳에도 속할 수 없기 때문에 -1이 출력되는게 맞지 않나요?

예를들어 밑의 테스트케이스 경우

7
1 2
1 3
1 4
2 3
2 4
5 6
6 7
5 7
-1 -1

1 2 4는 서로 아는사이고, 5 6 7도 서로 아는사이죠..

하지만 3은 1,2와는 아는사이지만 4와는 아는사이가 아니기 때문에 a 그룹에 속할 수 없고,(물론 1,2,4대신 1,2,3으로 묶어도 되겠네요!)

5,6,7과도 아는사이가 아니니 b 그룹에도 속할 수 없는 것이라고 생각했습니다.

저 경우의 출력이 -1이 아닌가요?!

작성하신 코드에서는 -1이 출력되지 않았던 것으로 기억합니다. 새 코드를 올려주실 수 있으신가요?

다른 사이트의 문제들을 푸느라 늦게 발견하였네요 죄송합니다.

새로 작성한 코드는 이렇습니다.

1. 만약 아는사이가 없는 사람이 두명이상 존재한다면 -1 출력후 return;

2. 유니온파인드를 하여 세 그룹으로 나뉜다면 -1출력후 return;(1은 1그룹에 반드시 포함된다고 가정)

3. arr_1 배열에는 루트가 1과 같은 사람들을 추가하는데, 현재까지 추가된 사람과의 관계를 인접배열로 판단하여 모두 아는사이일때만 추가.

4. 만약 추가하는 과정에서 루트가 1과 같지만 여태 추가된 사람중에 모르는 사이가 있다면 -1출력후 return

5. 나머지는 arr_2에 추가

6. arr_2에 추가된 사람들을 인접배열을 바탕으로 서로 아는사이인지 검사. 모르는사이라면 -1출력후 return

7. 리턴되지 않았다면 결과를 출력.

실수로 이전 코드를 올렸네요.. 새로 업데이트 된 코드입니다.

반례 드립니다.

2
-1 -1

수정후 주석 추가하였습니다.

그런데 n==2인 경우

1

1 -1

2 -1

이 출력이면 오답인가요??

2
1 2
-1 -1

아 위 케이스는 상관없습니다. n = 2인 경우 1과 2를 따로 놓으면 무조건 정답입니다

ㅠㅠ 여전히 테스트케이스를 만들어서 실행해보고있음에도 불구하고

17퍼센트에서 멈추네요

shiftpsh님의 도움을 받아 모든 가능성을 고려해서 고친것 같은데

무엇이 문제일까요 ㅋㅋㅋ..

반례 더 드립니다.

6
1 2
1 4
1 5
1 6
2 3
2 4
2 5
3 5
4 6
-1 -1

주신 반례에서의 출력은 -1이 아닌가요?

1번 그룹은 1,2,4 혹은 1,4,6이어야 하는데 이러면 6이나 2가 포함될 곳이 없지않나요?

아헐 이렇게묶을수가있구나 잠시만요

결국 모든 경우를 다 탐색해야하는 문제였네요..

감사합니다 shiftpsh님 주신 반례덕분에 해결했어요