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 |