백준 10451번: 순열 사이클

https://www.acmicpc.net/problem/10451

1. 문제

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 $\left(\begin{array}{cccccccc}1& 2& 3& 4& 5& 6& 7& 8\\ 3& 2& 7& 8& 1& 4& 5& 6\end{array}\right)$ 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해 $\left(\begin{array}{ccccc}1& \dots & i& \dots & n\\ {\pi }_1& \dots & {\pi }_i& \dots & {\pi }_n\end{array}\right)$ 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

2. 알고리즘

키워드 - DFS, BFS

3. 코드

#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <cstring>
using namespace std;
 
#define MAX_SIZE 100
#define INF 0x7fffffff
 
int board[1001];
int visited[1001];
 
void dfs(int i) {
 
    if (visited[i]) {
        return;
    }
 
    visited[i] = 1;
 
    dfs(board[i]);
}
 
/*
* @memory  - 1996 kb
* @time    - 36 ms
*/
int main() {
 
    std::ios::sync_with_stdio(false); cin.tie(0);
 
    int n; cin >> n;
 
    while(n--) {
        int d; cin >> d;
        
        for(int i=1; i<=d; i++) {
            cin >> board[i];
            visited[i] = 0;
        }
 
        int sol = 0;
        for(int i=1; i<=d; i++) {
            
            if (visited[i] == 0) {
                dfs(i);
                sol++;
            }
        }
 
        cout << sol << "\n";
 
        memset(visited, 0, sizeof(visited));
        memset(board, 0, sizeof(board));
    }
    return 0;
}