BOJ 1115 - 순열

BOJ 1115 - 순열

$B[0]=0$ 이다. $B[1]=A[B[0]]=A[0]$ 이다. $B[2]=A[A[0]]$ 이다.

즉, 0부터 시작해서 계속 변하는 싸이클이다.

$A[3]=4$ 이고 $A[4]=3$ 이 의미하는 것은 어떤 $B[k-1]=3$ 이나 $B[k-1]=4$ 가 나올 경우 그 다음은 무조건 $4$나 $3$이 나와서 싸이클이 형성된다는 것을 의미한다.

일단 순열 $\rm P$ 에서 싸이클의 개수를 세자. 싸이클의 개수가 $K$ 개라면 $K=1$ 인경우 정답은 $0$이고 아닐경우 $K$이다.

void solve() {  
   int n;  
   cin >> n;  
   vi P(n);  
   fv(P);  
  
   int c = 0;  
   vi vis(n);  
   for (int i = 0; i < n; i++) {  
      if (vis[P[i]]) continue;  
      int j = P[i];  
      c++;  
      do {  
         vis[j] = 1;  
         j = P[j];  
      } while (!vis[j]);  
   }  
   cout << (c == 1 ? 0 : c);  
}