双向链表练习题（2019牛客国庆集训派对day1）（二叉树）

双向链表练习题（2019牛客国庆集训派对day1）（二叉树）

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K Special Judge, 64bit IO Format: %lld

judge：双向链表练习题

题目描述

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{r}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{e}(L_{a_i}+L_{b_i})$, 其中 $\leftarrow$ 表示赋值，$+$ 表示列表的连接，$\mathrm{r}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{e}$ 表示列表的反转。例如，$\mathrm{r}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{e}([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$.

$1\le n,m\le 10^5$

$1\le a_i,b_i\le n,a_i\ne b_i$

$n$ 的总和，$m$ 的总和都不超过 $5\times 10^5$.

输出描述:

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

示例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

题解

根据点与点的相对关系建立二叉树，最后从根节点遍历，通过判断奇偶来判断左右孩子的输出顺序。

例如输入

5 3 2 3 2 4 5 2

则数据变化应该为

$cnt=1$ $(L[2],L[3])$ $lson[1]=N+3$ $rson[1]=N+2$ $L[2]=cnt=1$ $L[3]=0$$cnt=2$ $(L[2],L[4])$ $lson[2]=N+4$ $rson[2]=L[2]=1$ $L[2]=cnt=2$$cnt=3$ $$\begin{gathered} (L[5],L[2]) \\ lson[3]=L[2]=2 \\ rson[3]=N+5 \\ L[5]=cnt=3 \\ L[2]=0 \end{gathered}$$

图解应该是这样 1. 2. 3.

dfs的序应该为

$u=L[2]$ $$\begin{gathered} f=0 \\ a[1]=N+4 \end{gathered}$$$u=1$ $$\begin{gathered} f=1 \\ a[2]=N+2 \\ a[3]=N+3 \end{gathered}$$

而如果搜索以 $L[2]$ 为根节点的序列，那就从这里开始搜索： 并且通过判断奇偶可以判断左右孩子的输出顺序

答案应该是4 2 3

代码

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 5; int lson[N], rson[N]; int cnt = 0; int L[N]; int a[N], tot = 0; int n, m; void dfs(int u, int f) { if (u > N) { a[++tot] = u - N; return; } if (u == 0) return; if (f) { dfs(rson[u], f ^ 1); dfs(lson[u], f ^ 1); } else { dfs(lson[u], f ^ 1); dfs(rson[u], f ^ 1); } } int main() { // freopen("in","r",stdin); while (scanf("%d %d", &n, &m) == 2) { cnt = 0; for (int i = 1; i <= n; i++) L[i] = N + i; for (int i = 1; i <= m; i++) { int a, b; scanf("%d %d", &a, &b); cnt++; lson[cnt] = L[b]; rson[cnt] = L[a]; L[a] = cnt; L[b] = 0; } tot = 0; dfs(L[1], 0); printf("%d", tot); for (int i = 1; i <= tot; i++) { printf(" %d", a[i]); } puts(""); } return 0; }