#T250503. 魔法塔
魔法塔
题目描述:
灵王瑟兰迪尔要带领族人们迁徙到新大陆,临行前需要逐步关闭旧领地的魔法结界。 旧领地由N座魔法塔组成,这些塔通过M条双向魔法通道连接(1≤N,M≤200000)。为了 节省魔力,瑟兰迪尔计划逐次关闭魔法塔。每当一座塔被关闭时,所有连接它的魔法通 道都会失效,无法再使用。 现在需要判断:在每次关闭塔之前,剩余所有未关闭的塔是否构成一个连通的魔法网络 (即任意两座未关闭的塔之间都存在由未关闭通道组成的路径)。注意,当所有塔都关 闭后自然无需判断,但题目要求从初始状态开始,依次输出每次关闭前的连通性。
输入格式:
第一行:两个整数N,M,表示魔法塔数量和通道数量。 接下来M行:每行两个整数u,v,表示塔u和塔v之间有一条魔法通道。 最后N行:每行一个整数,表示第1到第N次被关闭的塔的编号(所有塔编号唯一,且为1 到N之间的整数)。
输出格式:
输出N行,第i行表示第i次关闭操作之前的连通性(第1行对应初始状态,第2行对应关闭第 1座塔之前的状态,依此类推)。若连通,输出 YES,否则输出 NO。
样例:
4 3
1 2
2 3
3 4
3
4
1
2
YES
NO
YES
YES
提示
(1≤N,M≤200000)
相关
在下列比赛中: