[백준 9466] 텀 프로젝트 (DFS) (C/C++) (★★★)

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
 
int T;
int N;
int map[100010];
int visited[100010]; // 0: 아직 시도안함 , -1: 팀을 찾음, 나머지: 팀을 못찾음 
bool flag;
vector<int> check; // 팀원 저장용
 
int stopMember;
 
void DFS(int start, int cnt)
{
    if(flag == true)
    {
        return;
    }
        
    if(visited[map[start]] == 0)
    {
        // 팀이 되는 경우에, 사람을 체크하기 위해서 
        check.push_back(map[start]);
        
        visited[map[start]] = cnt;
        DFS(map[start], cnt);
    }
    // 팀이 되는 경우 
    else if(visited[map[start]] == cnt)
    {
        // 처음과 끝이되는 멤버 체크 
        stopMember = map[start];
 
        flag = true;
        
        return;
    }
}
 
int main(void)
{
//    freopen("B9466_input.txt", "r", stdin);
    
    cin >> T;
    
    for(int k = 1; k <= T; k++)
    {
        for(int i = 0; i <= 100000; i++)
        {
            map[i] = 0;
            visited[i] = 0;
        }
        
        cin >> N;
        
        for(int a = 1; a <= N; a++)
        {
            int b;
            cin >> b;
            
            map[a] = b;
        }
        
        int cnt = 1;
        for(int i = 1; i <= N; i++)
        {
            check.clear();
            flag = false;
            
            // 혼자하고 싶어하는 경우 
            if(i == map[i])
            {
                visited[i] = -1;
                continue;
            }
            
            // 팀으로 할 가능성이 있는 경우 
            if(visited[i] == 0)
            {
                visited[i] = cnt;
                check.push_back(i);
                DFS(i, cnt);
                
                if(flag == true)
                {                    
                    // stopMember의 인덱스 찾기
                    int stopMemberIdx; 
                    for(int j = 0; j < check.size(); j++)
                    {
                        if(check[j] == stopMember)
                        {
                            stopMemberIdx = j;    
                            break;                
                        }
                    }    
                    
                    // stopMember부터 팀이 된 사람 -1 체크
                    for(int j = stopMemberIdx; j < check.size(); j++)
                    {
                        visited[check[j]] = -1;
                    }    
                } 
                
                cnt++;
            }
        }
        
        int ans = 0;
        for(int i = 1; i <= N; i++)
        {
            if(visited[i] != -1)
            {
                ans++;
            }
        }
        
        cout << ans << endl;
    }
    
    return 0;
}