백준 10451 순열 사이클 C++

https://www.acmicpc.net/problem/10451

그래프 정보를 배열로 받아주고, DFS를 돌려주면 된다.

DFS를 실행할 때, 방문한 지점을 다시 방문하는 것이 base condition이므로, DFS가 끝날 때 마다 사이클의 개수가 하나씩 늘어난다.

#include<iostream>
#include<vector>
using namespace std;
int v[1002];
bool vis[1002];
 
void dfs(int cur) {
    if (vis[cur]) return; //이미 방문한 곳을 재방문 했다는 건 사이클이라는 뜻
 
    vis[cur] = true;
    int next = v[cur];
    dfs(next);
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        
        for (int i = 1; i <= n; i++) 
            cin >> v[i];
        
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && v[i] != 0) {
                cnt++;
                dfs(i);
            }
        }
        cout << cnt << '\n';
 
        for (int i = 1; i <= n; i++) 
            vis[i] = false;
        
    }
 
    return 0;
}