有一串从左到右编号分别为 i 的小球，其中 i ≥ 1。(A, 1, 3) 代表将 1 号小球移动到 3 号小球的左边，(B, 1, 3) 则代表将 1 号小球移动到 3 号小球的右边。输入的数值为小球个数 n，指令条数 m。

具体代码及注释如下：
[cc lang = “cpp” escaped = “true”]
#include
#include
#include

using namespace std;

// 该函数代表将编号分别为 x 和 y 的小球们相连
void link(int x, int y, vector &left, vector &right) {
right[x] = y;
left[y] = x;
}

int main(void) {
int n, m;
cin >> n >> m;

// 分别定义左、右连接数组，用于存储每个小球左边和右边的小球编号
vector<int> left(n+1);
vector<int> right(n+1);
for (int i = 1; i <= n; i++) {
    left[i] = i-1;
    right[i] = i + 1;
}
right[n] = 0;

char c;
int ball1, ball2;
while (m--) {
    cin >> c >> ball1 >> ball2;
    link(left[ball1], right[ball1], left, right);
    if (c == 'A') {
        link(left[ball2], ball1, left, right);
        link(ball1, ball2, left, right);
    }
    // B 操作其实与 A 操作是相对的
    else {
        link(ball1, right[ball2], left, right);
        link(ball2, ball1, left, right);
    }
}

int ind;
// 寻找最左边的小球
for (int i = 1; i <= n; i++)
    if (left[i] == 0) {
        ind = i;
        break;
    }
// 输出
while (right[ind] != 0) {
    cout << ind << ' ';
    ind = right[ind];
}
cout << ind << ' ' << endl;

return 0;

}
[/cc]

个人认为这道题的关键有两点：

• 理解 link 函数
• 注意数组的下标

至于 link 函数怎么理解，emmmmm，大家意会一下。在写这个函数之前，我们要给其定义，即它要解决什么问题，这里解决的是“将编号分别为 x 和 y 的小球们相连”。带着这个定义再使用它时就很容易理解了，例如：代码第 30 行。