6장 그래프 - (3) 그래프 탐색 문제 3 - 순열 사이클(10451번)

1. 순열 사이클

- 순열이 주어졌을 때, 순열 사이클의 개수를 찾는 문제

- 이전에 풀어봤던 연결 요소 문제와 유사

- 이 문제의 경우, 각 정점마다 하나의 간선만 존재하므로 인접행렬이나 인접리스트로 구현하지 않아도 됨

- 1차원 배열로 각 정점에 연결된 정점을 저장해서 구현

2. 문제 정답

#include <iostream>

using namespace std;

int a[1001]; // a[i]는 i번 정점에 연결된 정점

int check[1001]; 

void dfs(int x){

if(check[x]==true){

return;

}

check[x]=true;

dfs(a[x]);

}

int main(void){

int t;

cin >> t;

while(t--){

int n;

cin >> n;

for(int i=1;i<=n;i++){

cin >> a[i];

check[i]=false;

}

int ans = 0;

for(int i=1;i<=n;i++){

if(check[i]==false){

dfs(i);

ans++;

}

}

cout << ans << '\n';

}

return 0;

}