BOJ 1115 - 순열
이다. 이다. 이다.
즉, 0부터 시작해서 계속 변하는 싸이클이다.
이고 이 의미하는 것은 어떤 이나 가 나올 경우 그 다음은 무조건 나 이 나와서 싸이클이 형성된다는 것을 의미한다.
일단 순열 에서 싸이클의 개수를 세자. 싸이클의 개수가 개라면 인경우 정답은 이고 아닐경우 이다.
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);
}
Comments