[C++] 백준 10451 순열 사이클

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

10451번: 순열 사이클

 

문제 해결

• 재귀를 이용해 사이클을 조사하는 것이다.
• 사이클이 만들어 지는 것을 확인 했으면 다음 만들 수 있는 것을 확인하는데 사이클 만들어지는데 구성 된 숫자는 다음 사이클을 만들 때 구성 될 수 없으므로 visited를 이용해 이미 구성 되었는 지를 확인하도록 한다.

 

CODE

#include <iostream>
#include <cstring>
using namespace std;
int T;
int N;
int A[1001];

void  cycle(bool visited[], int i);
int main() {
	cin >> T;
	for (int t = 0; t < T; t++) {
		cin >> N;
		for (int i = 1; i <= N; i++) {
			cin >> A[i];
		}
		int ans = 0;
		bool visited[1001] = { false };
		for (int i = 1; i <= N; i++) {
			if (not visited[i]) {
				cycle(visited,i);
				ans++;
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

void cycle(bool visited[], int i) {
	visited[i] = true;
	if (visited[A[i]] == false) {
		cycle(visited, A[i]);
	}
}