백준 10451번: 순열 사이클

[문제 링크]

10451번: 순열 사이클

---

입력으로 주어지는 순열과 1, 2, 3, ... N 순열은 서로 1:1 대응이라는 것을 알 수 있다.

따라서 입력받는 순서대로 1부터 N까지 정점을 연결한 다음, 모든 정점을 방문할 때 까지 dfs를 수행한 횟수를 출력하면 원하는 결과를 얻을 수 있다.

---

#include <iostream>
#include <vector>
using namespace std;

vector<int> adj(1001); // 1:1 그래프
vector<bool> visited(1001);

void dfs(int here) {
	visited[here] = true;
	int there = adj[here];
	if (!visited[there]) dfs(there);
}

int main(void) {
	int tc;
	cin >> tc;

	while (tc--) {
		int N;
		cin >> N;
		visited = vector<bool>(N + 1, false);

		for (int i = 1; i <= N; i++) {
			int num;
			cin >> num;
			adj[i] = num;
		}

		int cnt = 0;
		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {
				cnt++;
				dfs(i);
			}
		}

		cout << cnt << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 165 day