AT_abc219_g [ABC219G] Propagation

题目描述

给定一个有 $N$ 个顶点、$M$ 条边的简单无向图。$N$ 个顶点分别称为顶点 $1$、顶点 $2$、$\ldots$、顶点 $N$。
对于 $i=1,2,\ldots,M$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。
另外，对于 $i=1,2,\ldots,N$，顶点 $i$ 上写有整数 $i$。

有 $Q$ 个查询。
对于 $i=1,2,\ldots,Q$，第 $i$ 个查询用整数 $x_i$ 表示。在第 $i$ 个查询中，进行如下操作：

1. 设顶点 $x_i$ 上写的整数为 $X$。
2. 对于所有与顶点 $x_i$ 相邻的顶点，将它们上写的整数都改写为 $X$。

这里，顶点 $u$ 和顶点 $v$ 相邻，指的是存在一条连接顶点 $u$ 和顶点 $v$ 的边。

请在按输入顺序处理完所有查询后，输出每个顶点上写的整数。

输入格式

输入以如下格式从标准输入给出。

$N$ $M$ $Q$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
$x_1$ $x_2$ $\ldots$ $x_Q$

输出格式

请输出所有查询处理完毕后，每个顶点上写的整数，按顺序用空格隔开。
对于 $i=1,2,\ldots,N$，$A_i$ 表示顶点 $i$ 上写的整数。

$A_1$ $A_2$ $\ldots$ $A_N$

输入输出样例 #1

输入 #1

5 6 3
4 2
4 3
1 2
2 3
4 5
1 5
1 3 4

输出 #1

1 3 3 3 3

输入输出样例 #2

输入 #2

14 14 8
7 4
13 9
9 8
4 3
7 2
13 8
12 8
11 3
6 3
7 14
6 5
1 4
10 13
5 2
2 6 12 9 1 10 5 4

输出 #2

1 6 1 1 6 6 1 9 9 10 11 12 10 14

说明/提示

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq \min(2 \times 10^5, N(N-1)/2)$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• $1 \leq x_i \leq N$
• 给定的图是简单图，即不存在自环或重边。
• 输入均为整数。

样例说明 1

每个查询的操作如下：

• 第 1 个查询 $(x_1 = 1)$：顶点 1 上的整数为 1，与顶点 1 相邻的顶点为顶点 2 和顶点 5。因此，顶点 2 和顶点 5 上的整数都被改写为 1。
• 第 2 个查询 $(x_2 = 3)$：顶点 3 上的整数为 3，与顶点 3 相邻的顶点为顶点 2 和顶点 4。因此，顶点 2 和顶点 4 上的整数都被改写为 3。
• 第 3 个查询 $(x_3 = 4)$：顶点 4 上的整数为 3，与顶点 4 相邻的顶点为顶点 2、顶点 3 和顶点 5。因此，顶点 2、顶点 3、顶点 5 上的整数都被改写为 3。（顶点 2 和顶点 3 上已经是 3，实际上只有顶点 5 的整数发生了变化。）

由 ChatGPT 4.1 翻译