백준 10451 : 순열 사이클

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;
}