[10451] 순열 사이클

그래프에 있는 사이클을 구하는 문제다.

i번째 인덱스를 고정해놓고 1 부터 검사한다.

j = arr[i]로 초기화하고 이때 j(다음으로 이어질 숫자) 와 i(사이클의 첫번째 숫자)가 같을 때까지 j = arr[j]로 업데이트한다.

검사한 인덱스 에는 1을 대입해 중복 검사를 하지 않도록 한다.

j 와 i 가 같아지면 순열 사이클이 형성된것이므로 res에 1을 추가한다.

---

#include <cstdio>

using namespace std;

int main(){

int T,N;

int arr[1000];

int check[1000] = {};

int j = 0,res = 0;

scanf("%d",&T);

while(T > 0){

res = 0;

j = 0;

scanf("%d",&N);

for(int i = 1;i<=N;i++){

scanf("%d",&arr[i]);

check[i] = 0;

}

for(int i = 1;i<=N;i++){

if(check[i] != 1){

j = arr[i];

while(j != i){

check[j] = 1;

j = arr[j];

}

res++;

}

}

printf("%d\n",res);

T--;

}

}