https://www.acmicpc.net/problem/10451
★★☆☆☆
기존 dfs 개념을 활용하면 어렵지 않은 문제
순열은 각 정점이 하나의 정점만을 가리키게 되고,
예시 1의 경우 다음과 같은 순열을 얻게 되는데,
가리키는 정점을 계속 따라가다가, 이미 방문한 정점이 나오면 사이클이 발생한 것
이라는 아이디어를 사용해서 구현하였다.
이때, 가리키는 정점을 계속 따라간다는 개념은
깊이 우선 탐색 dfs의 개념과 유사하기 때문에 dfs적으로 접근하였다.
#include <iostream>
#define MAX 1001
using namespace std;
int* graph;
int n;
bool visited[MAX];
void init() {
for (int i = 0; i <= n; i++) {
visited[i] = false; //visited 초기화
}
}
void bfs(int start) {
visited[start] = true;
//cout << start << "\n";
if (!visited[graph[start]]) { //1개의 정점만 이어져 있으므로 반복문은 필요 x
bfs(graph[start]);
}
return;
}
int main() {
int t;
cin >> t;
for (int j = 0; j < t; j++) {
cin >> n;
init();
graph = new int[n + 1];
for (int i = 1; i <= n; i++) {
int tem;
cin >> tem;
graph[i] = tem;
}
int ret = 0;
for (int i = 1; i <= n; i++) {
//cout << i << "번째 실행=============\n";
if (visited[i] == false) { //방문하지 않았다면 새로운 사이클
bfs(i);
ret++;
}
}
cout << ret << "\n";
}
return 0;
}