[알고리즘] 백준 10451번: 순열 사이클 (C++)

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

10451번: 순열 사이클

바로 직전에 사이클을 문제를 풀어서 그런지 쉽게 재귀를 통해 풀 수 있었다.

1. 방문하지 않았던 노드들을 탐색하기 시작한다.
2. 방문하지 않은 노드로 탐색을 시작하면 바로 해당 노드의 방문을 체크한다.
3. 해당 노드가 가리키는 노드가 방문하지 않았으면 재귀를 통해 다음 노드로 간다.
4. 만약 가리키는 노드가 방문이 되어있으면 사이클이라는 뜻이므로 사이클의 개수 값을 더한다.

#include <iostream>
#define MAX 1000 + 1
using namespace std;

int arr[MAX];
bool visited[MAX];
int result;

void backTrack(int node) {
	visited[node] = 1;
	int next = arr[node];

	if (!visited[next]) {
		backTrack(next);
	}
	else {
		result++;
	}
}

void reset(int value) {
	for (int i = 1; i <= value; i++) {
		visited[i] = 0;
	}
}

int main() {
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		int n;
		cin >> n;
		result = 0;

		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
		}

		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				backTrack(i);
			}
		}

		cout << result << '\n';
		reset(n);
	}
	return 0;
}