[문제 링크]

 

10451번: 순열 사이클

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\  3

www.acmicpc.net


입력으로 주어지는 순열과 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

'알고리즘 > BOJ' 카테고리의 다른 글

백준 16234번: 인구 이동  (0) 2020.09.21
백준 1261번: 알고스팟  (0) 2020.09.21
백준 2573번: 빙산  (0) 2020.09.21
백준 11404번: 플로이드  (0) 2020.09.20
백준 1701번: Cubeditor  (0) 2020.09.20

+ Recent posts