Play Train题解

YangXiaopei · 2023-08-01 16:42:45 · 题解

题目传送门

题目大意：

有三种操作：

• 连接 x 和 y。

• 断开 x 和 y 的连接。

• 输出 x 所在链的长度和所有元素，以换行隔开。

Solution：

当我们看到“连接”，“链”等字眼时，我们必须想到一种数据结构——链表（不会请自己去搜博客）。

所以我们用链表模拟即可。

注意：

第二种操作用 STL 的链表不太好处理，建议用手写链表。

Code：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n, q, o, x, y;
int l[N], r[N];
const int HEAD = 0;
const int END = 1e5 + 1;
void link(int a,  int b){
    r[a] = b;
    l[b] = a;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        link(HEAD, i);
        link(i, END);
    }
    while(q--){
        cin >> o;
        if(o == 1){//操作1
            cin >> x >> y;
            link(x, y);
        }
        if(o == 2){//操作2
            cin >> x >> y;
            link(x, END);
            link(HEAD, y);
        }
        if(o == 3){//操作3
            cin >> x;
            int pos = x;
            int cnt = 1;
            int t = x;
            while(l[pos] != HEAD){
                pos = l[pos];
                cnt++;
            }
            while(r[t] != END){
                t = r[t];
                cnt++;
            }
            cout << cnt << " ";
            for(int i = pos; i != END; i=r[i]){
                cout << i << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}