백준 10451 순열 사이클

www.acmicpc.net/problem/10451

10451번: 순열 사이클

문제를 이해하는 것은 어렵지 않다. 인덱스를 돌면서 방문처리 해주는 간단한 문제였는데, 그래프의 탐색중 기초문제같다.

 

#include <iostream>
using namespace std;

int ar[1001], tc, n, cnt;
bool vis[1001];

void dfs(int cur) {
	if (vis[cur]) return;
	vis[cur] = true;
	dfs(ar[cur]);
}

int main() {
	cin >> tc;
	while (tc--) {
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> ar[i];
		fill(vis, vis + 1001, false); //돌 때마다 초기화
		for (int i = 1; i <= n; i++) {
			if (!vis[i]) { //방문하지 않았다면
				dfs(i); cnt++; //한 사이클이 다 될때까지 dfs
			}
		}
		cout << cnt << '\n'; cnt = 0;
	}
}