[BOJ] 10451. 순열 사이클

10451. 순열 사이클

1. 문제

2. 입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

3. 출력

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

4. 풀이

C++

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define MAX 1001

int T, N;
vector<int> graph[MAX];
int visited[MAX];

void dfs(int v)
{
    visited[v] = true;
    
    for (int i = 0; i < graph[v].size(); ++i)
    {
    	int next = graph[v][i];
        if (!visited[next]) dfs(next);
    }
}


int main()
{
    cin >> T;
    
    for (int i = 0; i < T; ++i)
    {
        cin >> N;       
        for (int j = 1; j <= N; ++j)
        {
            int a;
            cin >> a;
            
            graph[j].push_back(a);
        }
        
        int count = 0;        
        for (int k = 1; k <= N; ++k)
        {
            if (!visited[k])
            {
                dfs(k);
                ++count;
            }
        }
        
        cout << count << '\n';
        
        for (int i = 1; i <= N; ++i)
            graph[i].clear();
        memset(visited, 0, sizeof visited);
        
    }
}