双向链表练习题

题目链接：https://ac.nowcoder.com/acm/contest/1099/K

链接：https://ac.nowcoder.com/acm/contest/1099/K
来源：牛客网

题目描述

Bobo 有 n 个列表 L1,L2,…,LnL_1, L_2, dots, L_nL1​,L2​,…,Ln​.
初始时，LiL_iLi​ 仅包含元素 i, 即 Li=[i]L_i = [i]Li​=[i].
他依次执行了 m 次操作。第 i 次操作由两个整数 ai,bia_i, b_iai​,bi​ 指定, 每次操作分为两步：
1. Lai←reverse(Lai+Lbi)L_{a_i} leftarrow mathrm{reverse}(L_{a_i} + L_{b_i})Lai​​←reverse(Lai​​+Lbi​​), 其中 ←leftarrow← 表示赋值，+ 表示列表的连接，reversemathrm{reverse}reverse 表示列表的反转。例如，reverse([1,2]+[3,4,5])=[5,4,3,2,1]mathrm{reverse}([1, 2] + [3, 4, 5]) = [5, 4, 3, 2, 1]reverse([1,2]+[3,4,5])=[5,4,3,2,1].
2. Lbi←[]L_{b_i} leftarrow []Lbi​​←[]. 其中 [] 表示空的列表。
输出 m 次操作后， L1L_1L1​ 的元素。

输入描述:

输入文件包含多组数据，请处理到文件结束。

每组数据的第一行包含两个整数 n 和 m.

接下来 m 行，其中第 i 行包含 2 个整数 ai,bia_i, b_iai​,bi​.

* 1≤n,m≤1051 leq n, m leq 10^51≤n,m≤105
* 1≤ai,bi≤n,ai≠bi1 leq a_i, b_i leq n, a_i eq b_i1≤ai​,bi​≤n,ai​�​=bi​
* n 的总和，m 的总和都不超过 5×1055 imes 10^55×105.

输出描述:

对于每组数据，先输出 L1L_1L1​ 的长度 ∣L1∣|L_1|∣L1​∣，再输出 ∣L1∣|L_1|∣L1​∣ 个整数，表示 L1L_1L1​ 的元素。

示例1

输入

复制

2 1
1 2
2 1
2 1
3 3
3 2
3 2
1 3

输出

复制

2 2 1
0
3 2 3 1
题意：给你一个长度为n的链表，初始时第i个表中只有一个数i,m次操作，每次操作a b  讲a b两个链表相连并且翻转赋值为a 再将b赋值为空 最后问你链表1的大小和数 
思路：就是普通的双向链表，也可以用splay来做，在这就只说用链表的写法，用库函数list就可以解决这道题，但不能使用reverse函数，这个函数复杂度是O(n) 
会超时，用一个小技巧就能实现翻转。
试想：
翻转1 2区间 变为2 1 翻转3 4区间 变为 4 3
那么再次翻转 2 1 又变成了 1 2
           4 3 又变成了 3 4
所以存一下下次翻转会变成什么
假设此时链表1:1 2  那么下次翻转将变为2 1  存下这个状态
　　　　链表2:3 4  那么下次翻转将变为4 3  存下这个状态
此时执行链表1和2的连接和翻转 答案就是 4 3 2 1 
有没有发现就是 我们存下的下次翻转的状态相连 思想就是这个 ，看不懂的话 再看代码理解：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<cstdlib>
#include<fstream>
#include<time.h>
#include<list>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const LL INF=1e9+7;
const int maxn=1e5+50;
list<int>a[maxn],d[maxn];
int main()
{
    int N,M;
    while(scanf("%d%d",&N,&M)!=EOF)
    {

        for(int i=1;i<=N;i++)
        {
            a[i].clear();
            d[i].clear();
            a[i].push_back(i);
            d[i].push_back(i);
        }
        while(M--)
        {
            int u,v;scanf("%d%d",&u,&v);
            a[u].splice(a[u].end(),a[v]);
            d[v].splice(d[v].end(),d[u]);
            a[u].swap(d[v]);
            d[u].swap(d[v]);
            a[v].clear();
            d[v].clear();
        }
        cout<<a[1].size();
        list<int>::iterator it;
        for(it=a[1].begin();it!=a[1].end();it++) cout<<" "<<*it;cout<<endl;
    }
    return 0;
}