[BOJ 10451] 순열 사이클

동아리 초심자 오늘 문제 추천으로 가져온 문제이다. 그래프에서의 사이클은 자주 접해봤을 것이다. 그러나 순싸분으로 불리는 '순열 사이클 분할'이라는 개념에 대해서는 들어본 사람이 많이 없을 것이다. 그래서 이 개념을 소개하고자 들고 온 문제이다. 

 

순열 사이클의 개념 자체는 문제에 적혀있는 것과 동일하다. 개념 자체가 직관적으로 알 수 있고 문제 또한 그대로 구현하면 된다. 순열 사이클이라는 특수한 경우에 의해 in-out degree(들어오는 간선과 나가는 간선)이 하나이므로 구현 또한 간단하다. dfs를 통해 방문하지 않은 정점이 나올 때까지 돌려주면 된다. 각 정점은 한 번만 방문하므로 $O(N)$에 해결 가능하다.

 

코드 보기 ▼

int T, N, A[MAXN];
bool vst[MAXN];

void dfs(int x) {
    vst[x] = 1;
    if (!vst[A[x]])
        dfs(A[x]);
}

int main(void) {
    fastio;
    cin >> T;
    while (T--) {
        cin >> N;
        for (int i = 1; i <= N; i++)
            cin >> A[i], vst[i] = 0;

        int cnt = 0;
        for (int i = 1; i <= N; i++) {
            if (!vst[i]) {
                cnt++;
                dfs(i);
            }
        }
        cout << cnt << "\n";
    }
    return 0;
}

사실 이 개념 그대로 사용하는 경우는 거의 없고, 주로 순열 사이클 분할의 성질에 관련한 문제가 나온다. 두 원소의 위치를 교환할 때, 달라지는 cycle의 개수, inversion의 개수 등이 그러한 성질에 속한다. 작년 KUPC 문제로 출제되었던 양손 정렬 문제 https://www.acmicpc.net/problem/30465를 풀어보면서 성질을 알아보자.