[AC] 9466 텀 프로젝트

출처 : https://www.acmicpc.net/problem/9466

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/9466.cpp

이 문제는 단순히 사이클을 찾고 끝내는 문제라고 생각했다. 그러나 학생이 무려 10만명이기 때문에 이중포문만 돌려도 TL을 피할 수 없다.

그래서 한번에 하는 방법을 생각해봤는데 O(n)은 사실상 불가능하고 내생각엔 O(2n)정도가 최대일것 같다. 

방법은 다음과 같다.

1번학생부터 n번학생까지 포문을 돌리되 1번학생과 연관된 모든 학생을 체크하면서 지워나간다. 이때 써클이 되는지 안되는지는 번호를 부여함으로써 알 수 있다. 써클이 되면 사용된 학생을 다시 돌아오게되고 이때 이 학생 직전에 몇번을 부여했는지를 파악하면 된다. 써클이 되지 않는 경우는 존재하지 않는다. 반드시 어디선가는 끝나야하기 때문이다. 

위와 같은 방법을 사용하면 빠르게 끝낼 수 있다.