A30866.【算法】一场地震引发的题目

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

青青草原经历了百年难遇的地震,破坏程度相对厉害,以至于Gold King的农场损失惨重,现在想召集所有农场管理员来集合。

    但幸运的是,Gold King家P(1  <= P  <= 30,000)个农场有些还能使用,农场编号为1..P,有C(1  <= C  <= 100,000)条双向路径连接农场。路径编号为1..C,每条路径i连接农场a_i和b_i (1  <= a_i <= P;1  <= b_i  <= P),因为数据比较粗糙,路径可能连接a_i到它自己,或者两个农场间有多条路径

输入格式

第一行输入三个数P、C、N,表示有P个农场,C条路径,N个管理员。
接下来输入C行,每行输入两个数据a_i 和 b_i。

  再往下输入N行,每行输入一个整数j,表示农场标号。

输出格式

输出一个数,表示最少不能回到大本营的农场的数目(包括损坏的牛棚)。

输入输出样例

  • 输入#1

    4 3 1
    1 2
    2 3
    3 4
    3
    

    输出#1

    3
    

说明/提示

“某个点没有坏,但是无法到达1号点”
那与它相邻的点,要么是坏点,要么和它一样。

  这里假设相邻的点全都是坏点即可,无需考虑相邻点的相邻点情况。
首页