BOJ 1115 - 순열

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

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

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

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

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);  
}

Tags:

Categories:

Updated:

Comments