섞기 순열

백준 2487번: 섞기 순열

아이디어

사이클 크기 모두 찾고 그 크기간의 최소공배수를 구하면 정답.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 20001;
int N;
int arr[MAX];
bool visited[MAX];

int gcd (int a, int b) {
    if (!b) return a;
    return gcd(b, a%b);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }

    vector<int> v;

    for (int i = 1; i <= N; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        int cur = i;
        int next = arr[i];
        int cnt = 1;
        while (next != cur) {
            visited[next] = true;
            cnt++;
            next = arr[next];
        }
        v.push_back(cnt);
    }

    long long lcm = 1;
    for (int& x : v) {
        // cout << x << ' ';
        lcm = lcm*x/gcd(lcm, x);
    }

    cout << lcm;

    return 0;
}

여담

최소공배수를 구하기 위해 곱하는 과정에서 int 범위를 초과할 수 있다.