[백준 10451번] 순열 사이클 (C++)

문제링크 : https://www.acmicpc.net/problem/10451

10451번: 순열 사이클

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

vector <int> arr[1001];
bool check[1001];


void dfs(int n)
{
    check[n]=true;
    for(int i=0; i<arr[n].size(); i++)
    {
        if(!check[arr[n][i]])  //연결된 값 확인
        {
            dfs(arr[n][i]);
        }
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T, size;
    cin >> T;
    while(T--)
    {
        cin >> size;

        memset(check, 0, sizeof(check));  //초기화
        memset(arr, 0, sizeof(arr));

        for(int i=1; i<=size; i++)
        {
            int n;
            cin >> n;
            arr[i].push_back(n);  //방향 그래프 
        }

        int cnt=0;
        for(int i=1; i<=size; i++)
        {
            if(!check[i])
            {
                dfs(i); //사이클 탐색
                cnt++;
            }
        }
        cout << cnt << "\n";
    }
    
    return 0;
}

인덱스 순서에 맞게 각 배열에 순열 값을 담고 이를 dfs 탐색을 통해 확인했다.

처음 값을 시작으로 통과한 값은 check 해주고, 연결된 값을 이어서 탐색하는데 연결된 값이 이미 탐색했다면 사이클이 만들어진 것이므로 dfs 탐색을 종료하고 카운트를 증가시켜준다.