A7685. [ABC305E] Art Gallery on Graph
编程题
普及/提高-
知识点
题目描述
给定一张 $N$ 个点（编号为 $1 \sim N$），$M$ 条边的无向图，保证无重边无自环。现在有 $K$ 个被标记的点，其中第 $i$ 个被标记的点的编号为 $p_i$，任何从 $p_i$ 出发经过不超过 $h_i$ 条边能到达的点都会被染色（包括 $p_i$ 自身）。你需要求出这张图最终有哪些点被染色。
输入格式
第一行分别为 $N$ , $M$ , $K$ 。
接下来 $M$ 行，每行两个正整数 $a_i, b_i$ ，表示编号为 $a_i, b_i$ 的点连有一条无向边。
接着 $K$ 行，每行两个整数 $p_i$ , $h_i$ 表示编号为$p_i$ 的点将会从自己出发经过不超过 $h_i$ 条边进行染色。
接下来 $M$ 行，每行两个正整数 $a_i, b_i$ ，表示编号为 $a_i, b_i$ 的点连有一条无向边。
接着 $K$ 行，每行两个整数 $p_i$ , $h_i$ 表示编号为$p_i$ 的点将会从自己出发经过不超过 $h_i$ 条边进行染色。
输出格式
第一行一个数字 $G$，表示被染色的点的个数。
第二行 $G$ 个数字，表示被染色的点，按照从小到大的顺序输出。
第二行 $G$ 个数字，表示被染色的点，按照从小到大的顺序输出。
输入输出样例
输入 #1
5 5 2 1 2 2 3 2 4 3 5 1 5 1 1 5 2
输出 #1
4 1 2 3 5
输入 #2
3 0 1 2 3
输出 #2
1 2
输入 #3
10 10 2 2 1 5 1 6 1 2 4 2 5 2 10 8 5 8 6 9 6 7 9 3 4 8 2
输出 #3
7 1 2 3 5 6 8 9
说明/提示
$1 \le N \le 2 \times 10^5$，$0 \le M \le 2 \times 10^5$，$1 \le K,a_i,b_i,p_i,h_i \le N$，$p_i$ 互不相同。
保证给定的图无重边，无自环。
保证给定的图无重边，无自环。