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