CF847A 题解

NaOHqwq · 2023-08-24 22:23:19 · 题解

题意

题面有一点点长，但其实就是给出几个双向链表，让我们把这些链表连成一条，且只能通过链接两个双向链表的首尾单元来链接这两个双向链表。

思路

模拟，只需要让每一条链表的头连向上一个尾，在把尾的值存下来就可以让这些链表连成一条了。

这里笔者就直接用数组模拟了，因为会比较简单。（也是因为笔者比较菜）

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100+5; 
int a[maxn], b[maxn];
int n, nxt;//nxt是存尾的变量
int main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i] >> b[i];
    }
    for(int i = 1;i <= n;i++){
        if(a[i] == 0){
            b[nxt] = i;
            a[i] = nxt;
            nxt = i;
            while(b[nxt]){
                nxt = b[nxt];
            }//链接两个链表的头尾
        }
    }   
    for(int i = 1;i <= n;i++){
        cout << a[i] << " " << b[i] << endl;
    }
    return 0;
}