[210604][백준/BOJ] 10451번 순열 사이클

문제

입출력

풀이

순열 그래프 내에서 순열 사이클이 몇개 있는지 구하는 문제이다.

1. DFS로 모든 시작점으로부터 탐색을 한다.
2. vis를 통해 방문했는지 여부를 확인하며 방문하지 않았다면 cnt++를 하며 탐색을 한다.
3. 최종 cnt 값이 순열 사이클의 개수이다.

코드

#include <bits/stdc++.h>
using namespace std;
#define SIZE 1002

int board[SIZE];
bool vis[SIZE];

void DFS(int V)
{
	vis[V] = 1;
	int nxt = board[V];

	if (!vis[nxt])
		DFS(nxt);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while (t--)
	{
		int n, cnt = 0;
		cin >> n;

		for (int i = 1; i <= n; ++i)
			cin >> board[i];
		
		for (int i = 1; i <= n; ++i)
		{
			if (!vis[i])
			{
				DFS(i);
				cnt++;
			}
		}
		cout << cnt << '\n';
		fill(vis, vis + SIZE, 0);
	}
}