cycle 찾기

#include <bits/stdc++.h>
using namespace std;

int arr[100001];
bool vis[100001];
bool done[100001];

int cnt= 0;
void DFS(int x) {
    vis[x] = 1;
    int nx = arr[x];

    if (!vis[nx]) {
        DFS(nx);
    }
    else if(!done[nx]) {
        for (int i = nx; i != x; i = arr[i]) {
            cnt++;
        }
        cnt++;
    }

    done[x] = 1;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    int t;
    cin >> t;
    for (int T = 0; T < t; T++) {
        int n;
        cin >> n;

        memset(arr, 0, sizeof(arr));
        memset(vis, 0, sizeof(vis));
        memset(done, 0, sizeof(done));

        cnt = 0;

        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
        }

        
        for (int i = 1; i <= n; i++) {
            if (!vis[i]) {
                DFS(i);
            }
        }

        cout << n - cnt << '\n';
    }


    return 0;
}

DFS로 O(n)으로 cycle을 찾아 낼 수 있다