NOIP2015 향상팀 두 번째 문제 정보 전달 [도론]

제목 설명
n명의 학우(번호 1부터 n까지)가 정보 전달 게임을 하고 있다.게임에서 모든 사람은 고정된 정보 전달 대상이 있는데 그 중에서 번호가 i인 학우의 정보 전달 대상은 번호가 Ti 학우이다.
게임이 시작되었을 때, 모든 사람은 자신의 생일만 알았다.이후 매 라운드마다 모든 사람은 자신이 현재 알고 있는 생일 정보를 각자의 정보 전달 대상에게 동시에 알려준다(주의: 누군가는 몇 명에게서 정보를 얻을 수 있지만 한 사람당 한 사람, 즉 자신의 정보 전달 대상에게만 알려준다).누군가가 다른 사람의 입에서 자신의 생일을 알게 되면 게임은 끝난다.실례지만 이 게임은 모두 몇 라운드를 진행할 수 있습니까?
입력 출력 형식
입력 형식: 총 2줄을 입력합니다.
첫 번째 줄에는 n 개인을 나타내는 양의 정수 n이 있습니다.
두 번째 행에는 공백으로 구분된 양의 정수 T1, T2,......n이 포함되어 있으며 Tn의 i번째 정수 Ti 표시 번호는 i입니다.
의 학우의 정보 전달 대상은 Ti 번호의 학우, Ti ≤n 및 Ti≠i
데이터는 게임이 반드시 끝날 것을 보증한다.
출력 형식: 출력은 모두 1줄로 1개의 정수를 포함하여 게임이 모두 몇 라운드를 진행할 수 있는지 나타낸다.
출력 샘플 가져오기
샘플 입력 #1:5 2 4 2 3 1 출력 샘플 #1:3

이 문제를 처음 풀었을 때 아무런 생각이 없었지만 처음부터 도론이라고 생각했고 인접 매트릭스로 할까 아니면 체인식 전방향 별로 할까 고민했다. 그러나 인접 매트릭스는 판단할 때마다 O(n2)이다. 횟수가 가장 많은 것은 체인식 전방향 별 공간의 복잡도가 O(n2)에 달했고 직접적으로 공간을 폭발시켰다. 나중에 생각해 보니 되돌아오는 것이 하나의 고리이기 때문에 불가능한 사람을 먼저 차버릴 수 있다.그리고 모든 고리 중 가장 작은 것을 직접 찾아라.

코드:

#include
using namespace std;
int n,i,r,l,d,k,ans,f[200010],p[200010],a[200010],q[200010];
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        f[a[i]]++;//f 
    }
    for(i=1;i<=n;i++)
        if(f[i]==0)q[++l]=i;//0 ， 
    r=l;
    l=0;
    while(lq[l]];
        f[d]--;
        if(f[d]==0){
            r++;
            q[r]=d;
        }
    }
    for(i=1;i<=r;i++)
        p[q[i]]=1;// 
    memset(f,0,sizeof(f));
    ans=(int)1e9;// 
    for(i=1;i<=n;i++)
        if(p[i]==0&&f[i]==0){
            k=1;
            d=i;
            while(a[d]!=i){
                d=a[d];
                k++;
            }
            d=i;
            ans=min(ans,k);
            while(a[d]!=i){
                f[d]=k;
                d=a[d];
            }
            f[d]=k;// 
        }
    printf("%d",ans);
    return 0;
}