問題概要

最初、箱 $1, 2, \dots, N$ にそれぞれボール $1, 2, \dots, N$ が入っている。

次の $M$ 回の操作を行う。 $i$ 回目の操作では、ボール $X_{i}$ が入っている箱から、ボール $X_{i}$ を取り出して、それを箱 $Y_{i}$ に入れる。

操作後に、ボール $1, 2, \dots, N$ がそれぞれどの箱に入っているかを答えよ。

制約

$1 \le N, M \le 2000$

解法

このような問題では、次のようなデータ box_to_balls を管理したくなるかもしれません (最終的にこのデータは不要になります)。

box_to_balls[v] ← 箱 $v$ に入っているボールの集合

ここで、1 つの箱には複数個のボールが入っているようなことが発生しうることに注意しましょう。よって、このデータ box_to_balls は、C++ であれば vector<vector<int>> 型で表現するのが通常だと思われます。

......しかし、この情報 box_to_balls を持っていても、操作の実装が難しいのです。なぜならば、 $i$ 回目の操作のときに、ボール $X_{i}$ がどの箱に入っているのかを特定する必要があるためです。

データの持ち方を工夫する

そこで、逆に「各ボールがどの箱に入っているのか」を管理してみましょう。具体的には、次のデータ ball_to_box を管理します。

ball_to_box[v] ← ボール $v$ が入っている箱の番号

今度は、ボール $v$ が入っている箱は一意に決まるため、ball_to_bax はシンプルに vector<int> 型 (C++ では) で表現できます。

このとき、ボール $X_{i}$ を箱 $Y_{i}$ に入れる操作は、次のように簡潔に記述できるのです！！！

ball_to_box[X[i]] = Y[i];

あとは、このような操作を $M$ 回実施すればよいでしょう。

コード

コードでは 0-indexed で実装しました。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    
    // 最初は、ボール i は箱 i に入っている
    vector<int> ball_to_box(N);
    for (int i = 0; i < N; ++i) ball_to_box[i] = i;
    
    // M 回の操作を行う
    for (int i = 0; i < M; ++i) {
        int X, Y;
        cin >> X >> Y;
        --X, --Y;  // 0-indexed にする
        
        // ボールを移し替える
        ball_to_box[X] = Y;
    }
    
    // 出力
    for (int i = 0; i < N; ++i) {
        cout << ball_to_box[i] + 1 << endl;
    }
}