[백준 2487] 섞기 수열

문제

www.acmicpc.net/problem/2487

 

알고리즘

union find

 

풀이

섞기 수열이 주어질 때, 원래의 카드 순서로 돌아오기 위한 궤적을 구하는 문제입니다.

 

카드들이 턴마다 어디로 움직이는지 파악해야합니다. 카드들이 섞기 수열에 따라 움직이며 각 카드마다 제자리로 돌아와야합니다. 같은 사이클을 사용하는 카드들의 크기들을 파악한 후 사이클의 최소 공배수를 구하면 궤적이 나오게 됩니다. 아래 유니온 파인드에서 $p$는 자신의 부모를 나타내며, 만약 $p$값이 음수라면 그 인덱스가 부모임을 나타내며 절댓값은 해당 사이클의 크기를 나타내도록 구현했습니다.

 

코드

#include <bits/stdc++.h>
#include <numeric>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int N;
int p[20005];

int find(int x) {
    return p[x] < 0 ? x : (p[x] = find(p[x]));
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N;
    memset(p, -1, sizeof(p));
    rep(i, N) {
        int x;
        cin >> x;
        --x;
        int a = find(x);
        int b = find(i);
        if (a == b)
            continue;
        p[a] += p[b];
        p[b] = a;
    }
    int ans = 1;
    rep(i, N) {
        if (p[i] < 0) {
            ans = lcm(ans, -p[i]);
        }
    }
    cout << ans;

    return 0;
}