Description Bobo 有 n 个列表 L1, L2, …, Ln. 初始时,Li 仅包含元素 i, 即 Li = [i]. 他依次执行了 m 次操作。第 i 次操作由两个整数 ai, bi 指定, 每次操作分为两步: Lai ← reverse(Lai + Lbi), 其中 ← 表示赋值,+ 表示列表的连接,reverse 表示列表的反转。例如,reverse([1, 2] + [3, 4, 5]) = [5, 4, 3, 2, 1]. Lbi ← []. 其中 [] 表示空的列表。 输出 m 次操作后, L1 的元素。 Input 输入文件包含多组数据,请处理到文件结束。 每组数据的第一行包含两个整数 n 和 m. 接下来 m 行,其中第 i 行包含 2 个整数 ai, bi. 1 ≤ n, m ≤ 105 1 ≤ ai, bi ≤ n, ai ≠ bi n 的总和,m 的总和都不超过 5 × 105. Output 对于每组数据,先输出 L1 的长度 |L1|,再输出 |L1| 个整数,表示 L1 的元素。 Sample Input 2 1 1 2 2 1 2 1 3 3 3 2 3 2 1 3 Sample Output 2 2 1 0 3 2 3 1
时间: 2023-05-24 17:04:06 浏览: 154
解题思路:
首先,分析题目可以得出,每个操作都只涉及到两个列表,因为只有两个参数,且每次清空 Lbi。因此,我们可以使用邻接表来存储这些列表之间的关系。
其中,每个邻接表中存储了与该节点相邻的节点(即执行过操作的节点)。邻接表可以用 unordered_map 来实现,键为节点编号,值为 vector<int> 类型的邻接表。
那么,如何处理这些操作呢?对于一次操作,我们只需将 La 和 Lb 反转,然后将反转后的 La 指向 Lb,将 Lb 置为空即可。反转可以用 reverse() 函数。
最后,我们只需从 L1 开始,依次遍历相邻节点,即可得出 L1 的元素。
代码实现:
阅读全文