AOJ 0011 Drawing Lots

問題概要

w個の縦棒、n個の横棒で構成されるあみだくじがある。
横棒iは、a_iとb_iをつなぐ。
横棒は、上に存在するものから与えられる。

制約

• w ≤ 30
• n ≤ 30

解法

まず、始めに横棒が1本もない場合を考える。
その場合、i番目の縦棒から始めるとi番目の縦棒へと行き着くことは明らかである。

次に、1つの横棒があり、縦棒1と縦棒2をつなぐとすると、縦棒1から始めると縦棒2へと行き着き、縦棒2から始めると縦棒1へと行き着く。
つまり、2つの縦棒の結果を交換することになる。

複数の横棒がある場合でも、これが成り立つので、n個の横棒について、iが小さい順に交換を行うことで最終的な結果が得られる。

コード

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int w, n, a, b;
    char c;
    cin >> w >> n;
    vector<int> v(w);
    for (int i = 0; i < w; i++) {
        v[i] = i+1;
    }
    for (int i = 0; i < n; i++) {
        cin >> a >> c >> b;
        a--; b--;
        swap(v[a], v[b]);
    }
    for (int &x: v) {
        cout << x << endl;
    }
    return 0;
}