백준 9466 텀 프로젝트

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

check 배열에 cycle 이뤘는지 못 이뤘는지 기록해서, check 배열에 값이 있으면 더 조사 안하고 return 함

시간초과 많이 났는데 잘 고치고 디버깅했다

반례 이거 한 번 넣어보세요

1

10

2 3 4 5 6 1 3 7 8 9

출력 4 나와야 됩니다

 

#include <iostream>
#include<cstdio>
int T;
using namespace std;
int stu[100002];
int check[100002];
void makeNo(int goal,int cur) // cycle 못 이루는 거 기록
{
    if(check[cur]<0) return;
    if(goal==cur) return;
    check[cur]=-1; // cycle이 아닌 것은 -1
    makeNo(goal,stu[cur]);
}
void makeYes(int s, int cur) // cycle 이룬 거 기록
{
    if(s==cur||check[cur]<0) return;
    check[cur]=-2; // cycle인 것은 -2
    makeYes(s, stu[cur]);
}
void ans(int s, int cur, int visited[100002])
{
    if(s==cur)
    {
        makeYes(s,stu[s]);
        check[cur]=-2;
        return;
    }
    if(check[cur]<0)
    {
        makeNo(cur,s);
        return;
    }
    if(visited[cur]==1)
    {
        makeNo(cur,s);
        makeYes(cur,stu[cur]);
        check[cur]=-2;
        return;
    }
    visited[cur]=1;
    ans(s,stu[cur],visited);
}
int main()
{
    cin >> T; // 테스트 케이스 수
    while(T--)
    {
        int n;
        cin >> n;
        for(int i=1;i<=n;i++) scanf(" %d",&stu[i]);
        int visit[100002]={0,};
        for(int i=1;i<=n;i++)
        {
            if(check[i]<0) continue;
            visit[i]=1;
            ans(i,stu[i],visit);
            visit[i]=0;
        }
        int ct=0;
        for(int i=1;i<=n;i++) if(check[i]==-1) ct++;
        for(int i=1;i<=n;i++) // 
        {
            stu[i]=0;
            check[i]=0;
        }
        printf("%d\n",ct);
    }
}