백준] 10451 - 순열 사이클(ACM-ICPC Regionals Daejeon)

시간 제한 : 1초

메모리 제한 : 256MB

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

소스코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> arr;
vector<bool> check;
void sequence(int idx)
{
	if (check[idx] == false)
	{
		check[idx] = true;
		sequence(arr[idx]);
	}
	else
		return;
}
int main(void)
{
	int T;
	cin >> T;
	while (T--)
	{
		int N, cycle = 0;
		cin >> N;
		arr = vector<int>(N + 1, 0);
		check = vector<bool>(N + 1, false);
		for (int i = 1; i <= N; i++)
			cin >> arr[i];

		for (int i = 1; i <= N; i++)
		{
			if (check[i] == false)
			{
				cycle++;
				sequence(i);
			}
		}

		cout << cycle << '\n';
	}
}

Tip

수 하나가 다른 수 하나만 가리키기 때문에, 이미 거쳐간 숫자인지만 체크하면 되는 문제다.