BOJ 10451 순열 사이클

문제출처 : https://www.acmicpc.net/problem/10451

1. 문제요약

- 순열 사이클의 개수?

2. 접근방법

- 컴포넌트의 개수

3. 시간복잡도

- O(N)

4. 회고

소스코드 : dfs

#include<iostream>
#include<vector>
using namespace std;

int t, n;
vector<int> a;
vector<bool> check;

void dfs(int now){
	check[now] = true;

	if (!check[a[now]])
		dfs(a[now]);
}

int main(void){
	cin >> t;
	while (t--){
		cin >> n;
		a = vector<int>(n + 1);
		check = vector<bool>(n + 1, false);
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		int ans = 0;
		for (int i = 1; i <= n; i++)
			if (!check[i]){
				ans++;
				dfs(i);
			}
		cout << ans << "\n";
	}
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]