[ABC225D] Play Train

· · 题解

审题

现在有 Q 个操作，每个操作执行 3 种操作：

  1. 将 x 和 y 相连。
  2. 将 x 和 y 的连接解除。
  3. 输出 x 所在链的长度，及其这条链中的所有元素。

方法

【手写链表】看到题目就可以想到链表，此题用手写链表是再好不过的一个选择。

思路

相连，即 a 的左边是 b。连接解除，即 a 的左边不是 b，此时可以建立一个 0，使连接断开。输出时找到 0 就停止查找，输出链表长度，再进行第二次查找，输出每个元素。代码实现起来还是比较简单的。

代码

#include<bits/stdc++.h>
using namespace std;
const int NR = 2e5 + 5;
int n,q;
int x,y;
int a[NR];
int site,ans;
int l[NR],r[NR];
void link(int x,int y){ //连接
    r[x] = y;
    l[y] = x;
}
void dislink(int x,int y){ //断连
    if(r[x] == y) r[x] = l[y] = 0;
    else l[y] = r[x] = 0;
}
int main(){
    cin >> n >> q;
    while(q--){
        int op;
        cin >> op;
        if(op == 1){
            cin >> x >> y;
            link(x,y);
        }
        else if(op == 2){
            cin >> x >> y;
            dislink(x,y);
        }
        else if(op == 3){ //输出
            cin >> x;
            site = x,ans = 1;
            while(l[site] != 0) site = l[site]; //找到链头
            x = site; //复制，因为要用两次
            while(r[x] != 0){ //查找长度
                ans++;
                x = r[x];
            }
            cout << ans << " ";
            while(r[site] != 0){ //输出元素
                cout << site << " ";
                site = r[site];
            }
            cout << site << endl; //输出另外一个元素，然后换行
        }
    }
    return 0; //好习惯
}

不抄题解，从我做起！