A358. 一场地震引发的题目
编程题
普及/提高-
知识点
题目描述
青青草原经历了百年难遇的地震,破坏程度相对厉害,以至于Gold King的农场损失惨重,现在想召集所有农场管理员来集合。
但幸运的是,Gold King家$P$($1 \le P \le 30,000$)个农场有些还能使用,农场编号为$1..P$,有$C$($1 \le C \le 100,000$)条双向路径连接农场。路径编号为$1..C$,每条路径$i$连接农场$a_i$和$b_i$ ($1 \le a_i\le P;1 \le b_i \le P$),因为数据比较粗糙,路径可能连接$a_i$到它自己,或者两个农场间有多条路径。
Gold King现在在编号为$1$的大本营农场,有$N$ ($1 \le N \le P$)个农场的管理员通过手机短信发送$j$($2 \le j \le P$)汇报农场编号为j的农场没有损坏,但是他们无法通过路径和没有损坏的农场回到到大本营。当Gold King接到所有短信之后,想找出最小的不可能回到大本营的农场数目。这个数目包括损坏的农场。
但幸运的是,Gold King家$P$($1 \le P \le 30,000$)个农场有些还能使用,农场编号为$1..P$,有$C$($1 \le C \le 100,000$)条双向路径连接农场。路径编号为$1..C$,每条路径$i$连接农场$a_i$和$b_i$ ($1 \le a_i\le P;1 \le b_i \le P$),因为数据比较粗糙,路径可能连接$a_i$到它自己,或者两个农场间有多条路径。
Gold King现在在编号为$1$的大本营农场,有$N$ ($1 \le N \le P$)个农场的管理员通过手机短信发送$j$($2 \le j \le P$)汇报农场编号为j的农场没有损坏,但是他们无法通过路径和没有损坏的农场回到到大本营。当Gold King接到所有短信之后,想找出最小的不可能回到大本营的农场数目。这个数目包括损坏的农场。
输入格式
第一行输入三个数$P、C、N$,表示有$P$个农场,$C$条路径,$N$个管理员。
接下来输入$C$行,每行输入两个数据$a_i$ 和 $b_i$。
再往下输入$N$行,每行输入一个整数$j$,表示农场标号。
接下来输入$C$行,每行输入两个数据$a_i$ 和 $b_i$。
再往下输入$N$行,每行输入一个整数$j$,表示农场标号。
输出格式
输出一个数,表示最少不能回到大本营的农场的数目(包括损坏的牛棚)。
输入输出样例
输入 #1
4 3 1 1 2 2 3 3 4 3
输出 #1
3
说明/提示
“某个点没有坏,但是无法到达$1$号点”
那与它相邻的点,要么是坏点,要么和它一样。
这里假设相邻的点全都是坏点即可,无需考虑相邻点的相邻点情况。
那与它相邻的点,要么是坏点,要么和它一样。
这里假设相邻的点全都是坏点即可,无需考虑相邻点的相邻点情况。