백준에 순열 사이클 분할(permutation cycle decomposition)이라는 태그가 있어서 공부를 하게 되었다. 기본적인 개념은 다음과 같다. 어떤 순열 (a_1, a_2, \dots , a_n)이 있으면 a_i = f(i)인 함수가 있다고 생각해보자. f^2(i) = f(f(i))라고 할 때 i = f^k(i)인 1 \le k \le n을 찾을 수 있다. 그럼 k번 연산하는 과정에서 나온 수들을 모으면 (f(i), f^2(i), \dots, f^k(i))가 나올 것이고 이것을 하나의 순열 사이클이라고 한다. 순열 사이클 안에 존재하는 원소들은 모두 같은 순열 사이클이 될 것이다. 모든 원소에 대해 수행하면 여러개의 순열 사이클이 나오는데 이를 구하는 것을 순열 사이..