백준 10451번: 순열 사이클

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

10451번: 순열 사이클

문제 해결 방법은, 기본 DFS

방문 표시를 하면서 깊이 탐색하다보니, Main 문에서 실행되는 DFS 함수의 횟수는 순열의 개수와 같다.

백준 9466번 문제와 비슷하나, 9466번이 조금 더 어렵다.
10451을 풀어봣다면, 9466번을 꼭 풀어봤으면 좋겠다.
9466번 문제링크: https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

#include <iostream>
#include <cstring>

using namespace std;

int T;				// Test case 저장할 변수
int N;				// 순열의 크기
int nArr[1001];		// 순열을 저장 할 배열
bool bVisit[1001];

void DFS(int nStart)
{
	bVisit[nStart] = true;

	int next = nArr[nStart];


	if(!bVisit[next])
	{
		DFS(next);
	}
	
}
int main(void)
{
	cin >> T;

	for (int i = 0; i < T; i++)
	{
		int nCount = 0;
		cin >> N;
		
		memset(bVisit, false, sizeof(bVisit));
		
		for (int j = 1; j <= N; j++)
		{
			cin >> nArr[j];
		}

		for (int j = 1; j <= N; j++)
		{
			if (!bVisit[j])
			{
				DFS(j);
				nCount++;
			}
			
		}
		cout << nCount << endl;
	}
	return 0;
}