순열 사이클

작성일 | In

[백준] 10451번 - 순열 사이클

문제 링크

길이 n의 수열이 주어졌을 때, 이를 그래프화하여 사이클의 개수를 구하는 문제이다.
생각해보면 각 노드는 단 하나의 노드와 연결되며, 간선을 갖지 않는 노드는 없으므로 이 그래프에서 최소 하나 이상의 사이클이 존재한다.
즉, 어느 하나의 노드에서 탐색을 시작할 때, 아직 방문한 적 없는 노드일 경우 탐색을 진행하고, 이전에 방문한 노드를 만났을 때 탐색을 멈추면 그것이 하나의 사이클임을 알 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

void search(int num, vector<int>& adj, vector<bool>& visited) {
    int cur = num;
    while(!visited[cur]) {
        visited[cur] = true;
        cur = adj[cur];
    }
}

int main(void) {
    int t,n;
    scanf("%d", &t);

    while(t--) {
        scanf("%d", &n);

        vector<int> adj;
        vector<bool> visited;
        
        int ans=0;
        adj.resize(n+1);
        visited.resize(n+1, false);
        for(int i=1; i<=n; ++i) {
            int num;
            scanf("%d", &num);
            adj[i] = num;
        }

        for(int i=1; i<=n; ++i) {
            if(!visited[i]) {
                search(i, adj, visited);
                ++ans;
            }
        }

        printf("%d\n", ans);
    }
}
0%