[백준]Baekjoon10451(DFS)

문제링크 : https://www.acmicpc.net/problem/10451

#include <iostream>
#include <vector>

using namespace std;

int arr[1001];
bool check[1001];
int point; //맨 처음 cycle이 시작한 시작점 저장 
bool DFS(int start) {
	check[start] = true;
	int next = arr[start];
	if (check[next] == false) return DFS(next); //다음 노드가 탐색된 노드가 아니라면 탐색
	else { //다음 노드가 이미 탐색된 노드일 때
		if (next == point) return true; //시작 노드와 다음 노드가 같다면 cycle이 맞음
		else return false; //시작 노드와 다음 노드가 다르다면 cycle이 아님
	}
}
int main()
{
	int testcase; //테스트케이스의 갯수
	int N; //순열의 크기
	scanf("%d", &testcase);
	while (testcase--) {
		int count = 0; //순열 사이클의 갯수
		scanf("%d", &N);
		for (int i = 1; i <= N; i++) {
			scanf("%d", &arr[i]); //해당 노드가 가르키는 노드 저장
			check[i] = false; // check배열 초기화
		}
		for (int i = 1; i <= N; i++) {
			if (check[i] == false) {
				point = i; //시작 노드 저장
				if (DFS(i)) count++; // cycle이 맞다면 count증가
			}
		}
		printf("%d\n", count);

	}
}