순열 사이클 분해 (Permutation Cycle Decomposition)

정의

순열 사이클 분해는 순열 p[1..N]을 서로소(disjoint)인 사이클들의 곱으로 표현하는 것. 각 사이클 (a1 a2 … ak) 는 a1 -> p[a1] = a2, a2 -> p[a2] = a3, …, ak -> p[ak] = a1 을 의미.

문제 상황과 동기

순열을 함수 f(i) = p[i] 로 보면, 각 원소의 orbit 을 추적할 수 있다.

• 응용: 정렬 (swap 으로 정렬하는 최소 횟수 = N - 사이클 수), 치환 암호, 그룹 이론
• 최소 swap 정렬: 임의의 두 원소를 swap 할 때, N - (#cycles) 번이 최소

핵심 통찰: 순열은 방향 그래프로 볼 때 모든 정점의 out-degree = 1 이며, 각 연결 요소는 정확히 하나의 사이클을 이룬다.

시각화

핵심 아이디어

p = [3, 1, 2, 5, 4]  (1-indexed)

그래프:
  1 -> 3 -> 2 -> 1  (사이클, 길이 3)
  4 -> 5 -> 4       (사이클, 길이 2)

사이클 분해: p = (1 3 2)(4 5)

사이클 분해 알고리즘:

1. visited[1..N] = false
2. for i in 1..N:
3. if not visited[i]:
4. 새로운 사이클 시작
5. j = i
6. while not visited[j]:
7. visited[j] = true
8. 사이클에 j 추가
9. j = p[j]

알고리즘

find_cycles(p, N):
    visited = [false] * (N + 1)
    cycles = []
    for i = 1..N:
        if not visited[i]:
            cur = []
            j = i
            while not visited[j]:
                visited[j] = true
                cur.append(j)
                j = p[j]
            cycles.append(cur)
    return cycles

구현

// 순열 사이클 개수 세기, BOJ 10451
// 사이클 수 = N - (서로 다른 사이클 수)
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T; cin >> T;
  while (T--) {
      int n; cin >> n;
      vector<int> p(n + 1);
      for (int i = 1; i <= n; i++) cin >> p[i];
      vector<bool> vis(n + 1, false);
      int cycles = 0;
      for (int i = 1; i <= n; i++) {
          if (vis[i]) continue;
          cycles++;
          for (int j = i; !vis[j]; j = p[j])
              vis[j] = true;
      }
      cout << cycles << "\n";
  }
  return 0;
}

# 순열 사이클 개수 (BOJ 10451)
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
  n = int(input())
  p = [0] + list(map(int, input().split()))
  vis = [False] * (n + 1)
  cycles = 0
  for i in range(1, n + 1):
      if vis[i]: continue
      cycles += 1
      j = i
      while not vis[j]:
          vis[j] = True
          j = p[j]
  print(cycles)

// BOJ 10451: Count permutation cycles
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(br.readLine());
      while (T-- > 0) {
          int n = Integer.parseInt(br.readLine());
          int[] p = new int[n + 1];
          StringTokenizer st = new StringTokenizer(br.readLine());
          for (int i = 1; i <= n; i++) p[i] = Integer.parseInt(st.nextToken());
          boolean[] vis = new boolean[n + 1];
          int cycles = 0;
          for (int i = 1; i <= n; i++) {
              if (vis[i]) continue;
              cycles++;
              for (int j = i; !vis[j]; j = p[j])
                  vis[j] = true;
          }
          System.out.println(cycles);
      }
  }
}

2
8
3 2 7 8 1 4 5 6
5
2 1 4 3 5

3
3

복잡도

변형 / 활용

최소 swap 정렬

임의의 두 원소를 swap 하여 정렬할 때, 최소 swap 횟수 = N - (사이클 수). 각 사이클 (길이 k)는 k-1 번의 swap 으로 정렬 가능.

다음 순열 / 이전 순열

사이클 분해로 다음 순열(Next Permutation)과 이전 순열을 O(N) 에 계산 가능.

치환 행렬

순열 p 는 permutation matrix P 로 표현 가능. 사이클 분해는 P 의 Jordan 표준형과 연관.

함정

1. 1-indexed vs 0-indexed

C++ 배열이 0-indexed 라도 순열 문제는 1-indexed 표기가 편리. p[1..N] 을 사용하고 i 위치 주의.

2. visited 체크 순서

사이클 추적 시 while 순서: vis[j] 체크 후 j = p[j] 갱신. 아니면 무한루프.

3. 사이클 길이 1 처리

자기 자신을 가리키는 원소(p[i] == i) 는 길이 1 사이클. 정렬 관점에서 swap 0 회.

BOJ 연습 문제

참고

• 불변량 (permutation parity)
• 함수형 그래프
• DFS (깊이 우선 탐색)