9446번: 텀 프로젝트

보기보다 까다로운 문제다. (너무 지저분해서 내 코드를 완벽히 설명하기가 힘들 거 같다...)

#include <iostream>
#include <cstring>
 
int check[100001] = { 0 };
int skip[100001] = { 0 };
int map[100001] = { 0 };
int sum = 0;
 
void DFS(int stu[], int start, int cur, int seq) {
    check[cur] = seq;
 
    if(start == cur && skip[cur] != seq) {
        skip[cur] = seq;
        sum++;
        return;
    }
    if(stu[cur] == cur || check[stu[cur]] == seq || skip[stu[cur]] == seq) {
        check[stu[cur]] = 0;
        return;
    }
 
    DFS(stu, start, stu[cur], seq);
    if(skip[stu[cur]] == seq && sum > 0) {
        skip[cur] = seq;
        sum++;
    }
    else {
        check[stu[cur]] = 0;
    }
}
 
int main(void) {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    memset(check, 0, sizeof(check));
    memset(skip, 0, sizeof(skip));
    memset(map, 0, sizeof(map));
 
    int testCase;
    std::cin >> testCase;
 
    int len, seq = 0;
    for(int i = 0; i < testCase; i++) {
        std::cin >> len;
        sum = 0;
       seq = testCase + 1;
        for(int i = 1; i <= len; i++) {
            std::cin >> map[i];
        }
 
        for(int idx = 1; idx <= len; idx++) {
            if(skip[idx] == seq) continue;
            DFS(map, idx, map[idx], seq);
        }
        std::cout << len - sum << "\n";
    }
 
    return 0;
}