[C++] 백준 BOJ 10451 순열 사이클

문제 링크 : https://boj.kr/10451

그림과 같이 순열 사이클을 찾는 방법은 간단하다.

그냥 dfs로 돌리면 된다. dfs를 몇번 시작했는지만 체크하면 된다.

다음에 방문할 노드를 저장하는 것은 인접 리스트를 만드는 방법과 동일하고 방문했다면 0으로 설정하였다.

// BOJ 10451 순열 사이클
#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> permu;
 
void dfs(int idx){
    int next = permu[idx];
    if(next != 0) {
        permu[idx] = 0; // 방문 표시
        dfs(next);
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int tc;
    cin >> tc;
    while (tc--) {
        int num;
        cin >> num;
        permu = vector<int>(num + 1);
        for (int i = 1; i <= num; i++)
            cin >> permu[i];
 
        int result = 0;
        for(int i = 1; i <= num; i++){
            // 방문하지 않았으면 실행
            if(permu[i] != 0) {
                dfs(i);
                result++;
            }
        }
        cout << result << "\n";
    }
    return 0;
}