백준 10451 - 순열 사이클

문제

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

10451번: 순열 사이클

 

풀이

사이클을 이루는 그래프의 컴포넌트 수를 구하면 된다. 1번 정점부터 N번 정점까지 돌면서 dfs 탐색을 실행할 때 마다 컴포넌트 수를 추가해 준다. 그리고 각 정점은 한 개의 간선만 가지므로 1차원 배열로 그래프를 표현할 수 있다. 

 

 

코드

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