테스트 케이스라는 건 문제의 제한에 맞게만 들어있다면 어떤 게 들어있어도 상관 없습니다. 조건을 어기는 케이스가 있는 게 아닌 이상, "수정하는 게 좋다"라는 건 있을 수 없습니다. 오히려 어떤 케이스에 의해 코드들이 틀리거나 느려지게 만들 수 있다면, 그 케이스가 있는 것이 좋은 겁니다.

코드를 분석해보지는 않았지만 분명히 유의미한 차이가 있으니까 서로 다른 결과가 나왔을 것이고, 그건 코드의 잘못이지 테스트 케이스에는 아무런 잘못이 없습니다.

그럼 질문을 바꿔 어느 부분이 문제인지를 알 수 있을까요?

주석이 없어 죄송하긴 하지만

1. 입력을 받음
2. 역순으로 돌리며 Union find로 탐색
3. 그 결과를 출력 배열에 담음
4. 역순으로 출력

큰 구조는 이렇게 같습니다

보니까 두 번째 코드도 비효율적이어서 시간 초과가 나야 하는데 데이터가 약해서 통과된 것 같습니다.

데이터 추가를 요청하려고 합니다.

https://www.acmicpc.net/board/view/42233

조금 더 분석을 하자면, 첫 번째 코드는 경로압축을 전혀 하지 않기 때문에 랜덤으로 만든 데이터에 대해서도 쿼리당 평균 O(N)이 나오지만, 두 번째 코드는 쿼리에서 물은 정점들에 대해서만 경로압축이 이루어지는데 이는 평균 시간복잡도가 amortized O(1)이 될 것으로 보입니다. 그래서 저격 데이터를 손수 만들지 않으면 이처럼 뚫리기가 쉽습니다.

감사합니다. 더 열심히 해야겠네요.