백준:10451번 순열사이클

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

10451번: 순열 사이클

이 문제는 dfs를 이용한 문제인데 숫자를 n개 주어지면 1~n번째 숫자들이 주어진 숫자n개를 순서대로 가리키는 그래프를 만들어 낸다. 그리고 그래프에서 사이클 갯수를 구하는 문제이다.

여기서 사이클이란 숫자가 가리키는 곳으로 움직이다보면 목적지가 자기자신인게 사이클이다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<cstring>
#include<stack>
#include<queue>
#define PI 3.1415926535
using namespace std;
bool check1[1001] = { 0 };
bool check2[1001] = { 0 };
vector<int> d[1001];
int cnt = 0;
void dfs(int a) {
	check1[a] = true;
	for (int i = 0; i < d[a].size(); i++) {
		int next = d[a][i];
		if (check1[next] == false)
			dfs(next);
	}
}
void bfs(int a) {
	queue<int> q;
	check2[a] = true;
	q.push(a);
	while (!q.empty()) {
		int b = q.front();
		q.pop();
		cout << b << ' ';
		for (int i = 0; i < d[b].size(); i++) {
			int n = d[b][i];
			if (check2[n] == false) {
				check2[n] = true;
				q.push(n);
			}
		}
	}
}
int main()
{
	int t;
	cin >> t;
	while (t--) {
		int n;
		int cnt = 0;
		cin >> n;
		memset(check1, false, (n + 1) * sizeof(bool));      //초기화
		vector<int> a;          
		a.push_back(0);                  
		for (int i = 1; i <= n; i++) {              //초기화
			d[i].clear();
		}
		for (int i = 1; i <= n; i++) {               //값넣기
			int k;
			cin >> k;
			a.push_back(k);
		}
		for (int i = 1; i <= n; i++) {               //1~n번째를 a배열 값을 방향그래프로 표현
			d[i].push_back(a[i]);
		}
		for (int i = 1; i <= n; i++) {
			if (check1[i] == false) {              //사이클 개수 세기
				cnt++;
				dfs(i);
			}
		}
		cout << cnt << '\n';
	}
	
	return 0;
}