[백준/ DFS&BFS/ C++] 10451번 순열 사이클

문제보기

#include <bits/stdc++.h>

using namespace std;

int t, n;
vector<int> graph[1001];
bool visited[1001];
int result = 0;

void dfs(int x){
    visited[x] = true;

    for(int i=0; i<graph[x].size(); i++){
        int y = graph[x][i];
        if(!visited[y]) dfs(y);
    }
}

int main(void) {
    cin >> t; // 테스트케이스 수 입력

    for(int j=0; j<t; j++){
        cin >> n; // 순열의 수 입력
        for(int i=1; i<=n; i++){
            int x;
            cin >> x;
            graph[i].push_back(x); // i와 순열i의 간선 잇기
        }
        for(int i=1; i<=n; i++){
            if(!visited[i]){
                dfs(i); // dfs 수행
                result++; // 사이클 생길 때마다 +1
            }
        }
        cout << result << endl;
        result = 0;
        for(int i=1; i<=n; i++){ // visited와 graph 초기화
            visited[i] = false;
            graph[i].clear();
        }
    }

    return 0;
}