BOJ 10451번 순열 사이클

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/10451/10451/%EC%86%8C%EC%8A%A4.cpp

 

dfs 로 구현해보았다.

** 연결요소 체크하는 문제랑 거의 비슷하니 전체 방문을 확인해가며 풀면 된다.

 

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> v[1001];
bool visit[1001];
int T, N, vertex, check;
 
void dfs(int vertex) {
    if (visit[vertex]) return;
    visit[vertex] = 1;
    check--;
 
    dfs(v[vertex][0]);
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> T;
    while (T--) {
        cin >> N;
        for (int i = 1; i <= N; i++) {
            cin >> vertex;
            v[i].push_back(vertex);
        }
 
        check = N;
        int cnt = 0, start;
        while (check) {
            cnt++;
            for (int i = 1; i <= N; i++) {
                if (!visit[i]) {
                    start = i;
                    break;
                }
            }
            dfs(start);
        }
 
        cout << cnt << '\n';
        for (int i = 1; i <= N; i++) {
            visit[i] = 0;
            v[i].clear();
        }
    }
 
    return 0;
}