BOJ 9466 텀 프로젝트 C++

fill(startNumber, startNumber + n + 1, -1);
fill(countNumber, countNumber + n + 1, 0);​

9466번: 텀 프로젝트

시간초과로 를 고민하다가, 어차피 한번 방문한 노드는 다시 방문하지 않으니

fill(startNumber, startNumber + n + 1, -1);
fill(countNumber, countNumber + n + 1, 0);

부분을 반복문 밖으로 빼 해결하였다.
사이클을 판별할때 출발 노드가 같은것으로 판별하였고,
사이클안에 몇개의 노드가 포함되는지 확인하기 위해서 시작노드로부터 볓개의 노드를 세고 있는 지 카운팅해주었다.
노드가 자기 자신을 가리킬 때는 전체 갯수에서 1을 빼주고, 출발노드가 같아 사이클이 발견되었으나 자기 자신이 아닐 때는 카운트를 빼준것의 + 1만큼 빼주어 답을 구하였다

 

#include <bits/stdc++.h>
using namespace std;
int t;
int n;
bool vis[100003];
int student[100003];
int startNumber[100003];
int countNumber[100003];
int main() {
    cout.sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    while(t--) {
        cin >> n;
        int ans = n;
        fill(vis, vis + n + 1, false);
        fill(startNumber, startNumber + n + 1, -1);
        fill(countNumber, countNumber + n + 1, 0);
        for(int i = 1; i <= n; i++) {
            cin >> student[i];
        }
        for(int i = 1; i <= n; i++) {
            if(vis[i]) continue;
            queue<int> Q;
            Q.push(i);
            startNumber[i] = i;
            vis[i] = true;
            countNumber[i] = 1;
            while(!Q.empty()) {
                int cur = Q.front(); Q.pop();
                vis[cur] = true;
                int nextStudent = student[cur];
                if(startNumber[nextStudent] == startNumber[cur]) {
                    if(nextStudent == cur) {
                        ans = ans - 1;
                    }
                    else{
                        ans = ans - (countNumber[cur] - countNumber[nextStudent] + 1);
                    }
                    break;
                }
                if(vis[nextStudent]) continue;
                startNumber[nextStudent] = startNumber[cur];
                countNumber[nextStudent] = countNumber[cur] + 1;
                Q.push(nextStudent);
            }
        }
        cout << ans << '\n';
    }

    return 0;
}