题解 CF847A Union of Doubly Linked Lists

· · 题解

小兔的话

欢迎大家在评论区留言哦 \sim

简单题意

给出 n(n \leq 100) 个数的前驱和后继，每个数会与前驱和后继相连接，这些数会连接成一些旧链表
每条旧链表的起点都是前驱为 0（没有前驱）的数，终点都是后继为 0 （没有后继） 的数
请你把这些旧链表连接成 1 条新链表，并输出每个数在这条新链表中的前驱和后继（如果有多种连接方案，输出任意一种即可）

题目解析

题目已经给出了每个数的前驱和后继，并且每条链表的起点 都是前驱为 0 的数
我们先可以预处理出每条旧链表的起点和终点，就是从每一个前驱为 0 的数开始向后继搜索，一直搜索到没有后继为止，搜索中的第一个数为起点、最后一个数为终点
再把每条链表的终点和下一条链表的起点连接起来，最后就可以得到 1 条新链表了

样例分析

样例输入：
4 7
5 0
0 0
6 1
0 2
0 4
1 0

把旧链表预处理出来：3、5-2、6-4-1-7
把旧链表连接起来：3 \to 5-2 \to 6-4-1-7
连接之后，得出新链表：3-5-2-6-4-1-7 

样例输出:
4 7
5 6
0 5
6 1
3 2
2 4
1 0

代码（纯数组）

#include <cstdio>

int rint()
{
    int x = 0, fx = 1; char c = getchar();
    while (c < '0' || c > '9') { fx ^= (c == '-'); c = getchar(); }
    while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
    if (!fx) return -x;
    return x;
}

const int MAX_n = 100;
int n, now;
int u[MAX_n + 5]; // 前驱 
int v[MAX_n + 5]; // 后继 

int main()
{
    n = rint();
    for (int i = 1; i <= n; i++)
        u[i] = rint(), v[i] = rint();
    for (int i = 1; i <= n; i++)
    {
        if (u[i] == 0) // 没有前驱的肯定是一条子链表的起点 
        {
            v[now] = i; u[i] = now; now = i;
            // 与上一条子链表相连 
            while (v[now]) now = v[now]; // 向后搜索 
            // 循环结束, 找到当前子链表的终点 
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d %d\n", u[i], v[i]);
    return 0;
}

代码（vector）

#include <cstdio>
#include <vector>
using namespace std;

int rint()
{
    int x = 0, fx = 1; char c = getchar();
    while (c < '0' || c > '9') { fx ^= (c == '-'); c = getchar(); }
    while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
    if (!fx) return -x;
    return x;
}

const int MAX_n = 100;
int n;
int u[MAX_n + 5]; // 前驱 
int v[MAX_n + 5]; // 后继 
vector<pair<int, int> > e; // pair 记录每条子链表的头和尾 

int DFS(int now)
{
    if (v[now] == 0) return now; // 返回终点 
    return DFS(v[now]); // 向后搜索 
}

int main()
{
    n = rint();
    for (int i = 1; i <= n; i++)
    {
        u[i] = rint();
        v[i] = rint();
    }
    for (int i = 1; i <= n; i++)
        if (u[i] == 0) e.push_back(make_pair(i, DFS(i))); // 插入当前子链表 (简化版, 只留头和尾, 中间的没有影响) 
    int siz = e.size();
    for (int i = 1; i < siz; i++)
    {
        v[e[i - 1].second] = e[i].first;
        u[e[i].first] = e[i - 1].second;
        // 每条子链表与前一个子链表相连 
    }
    for (int i = 1; i <= n; i++)
        printf("%d %d\n", u[i], v[i]);
    return 0;
}