2019湖南省赛双向链表练习题

本文主要是介绍2019湖南省赛双向链表练习题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

双向链表练习题
Bobo 有 $n$ 个列表 $L_1, L_2, \dots, L_n$ . 初始时， $L_i$ 仅包含元素 $i$ , 即 $L_i = [i]$ . 他依次执行了 $m$ 次操作。第 $i$ 次操作由两个整数 $a_i, b_i$ 指定, 每次操作分为两步：

$L_{a_i} \leftarrow \mathrm{reverse}(L_{a_i} + L_{b_i})$ , 其中 $\leftarrow$ 表示赋值， $+$ 表示列表的连接， $\mathrm{reverse}$ 表示列表的反转。例如， $\mathrm{reverse}([1, 2] + [3, 4, 5]) = [5, 4, 3, 2, 1]$ .
$L_{b_i} \leftarrow []$ . 其中 $[]$ 表示空的列表。
输出 $m$ 次操作后， $L_1$ 的元素。

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

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

接下来 $m$ 行，其中第 $i$ 行包含 $2$ 个整数 $a_i, b_i$ .

$\leq n, m \leq 10^5$
$\leq a_i, b_i \leq n, a_i \neq b_i$
$n$ 的总和， $m$ 的总和都不超过 $\times 10^5$ .
输出格式
对于每组数据，先输出 $L_1$ 的长度 $L_1|$ ，再输出 $L_1|$ 个整数，表示 $L_1$ 的元素。

思路：
链表练习题。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <list>using namespace std;const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 7;
list<int>lst1[maxn],lst2[maxn];int main()
{int n,m;while(~scanf("%d%d",&n,&m)){for(int i = 1;i <= n;i++){lst1[i].clear();lst1[i].push_back(i);lst2[i].clear();lst2[i].push_back(i);}for(int i = 1;i <= m;i++){int x,y;scanf("%d%d",&x,&y);lst1[x].splice(lst1[x].end(),lst1[y]);lst2[y].splice(lst2[y].end(),lst2[x]);swap(lst2[x],lst2[y]);swap(lst1[x],lst2[x]);}int len = (int)lst1[1].size();printf("%d ",len);while(len--){printf("%d ",lst1[1].front());lst1[1].pop_front();}printf("\n");}return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <list>using namespace std;const int INF = 0x3f3f3f3f;
const int maxn = 100005;
int nex[maxn],lst[maxn];
int L[maxn],R[maxn],cnt[maxn];
int vis[maxn];void link(int x,int y)
{if(nex[x] == x && nex[y] == y){nex[x] = y;nex[y] = x;}else if(nex[x] == x && lst[y] == y){nex[x] = y;lst[y] = x;}else if(lst[x] == x && nex[y] == y){lst[x] = y;nex[y] = x;}else if(lst[x] == x && lst[y] == y){lst[x] = y;lst[y] = x;}
}int main()
{int n,m;while(~scanf("%d%d",&n,&m)){for(int i = 1;i <= n;i++){vis[i] = 0;cnt[i] = 1;lst[i] = nex[i] = i;L[i] = R[i] = i;}for(int i = 1;i <= m;i++){int x,y;scanf("%d%d",&x,&y);if(x == y){swap(L[x],R[x]);continue;}cnt[x] += cnt[y];cnt[y] = 0;if(L[y] == 0 && R[y] == 0){swap(L[x],R[x]);continue;}if(L[x] == 0 && R[x] == 0){L[x] = L[y];R[x] = R[y];swap(L[x],R[x]);L[y] = R[y] = 0;continue;}link(R[x],L[y]);R[x] = R[y];L[y] = R[y] = 0;swap(L[x],R[x]);}printf("%d ",cnt[1]);for(int i = L[1];i;){printf("%d ",i);vis[i] = 1;if(!vis[nex[i]]){i = nex[i];}else if(!vis[lst[i]]){i = lst[i];}else{break;}}printf("\n");}return 0;
}