bzoj 4229 选择
Description
现在,我想知道自己是否还有选择。 给定n个点m条边的无向图以及顺序发生的q个事件。 每个事件都属于下面两种之一: 1、删除某一条图上仍存在的边 2、询问是否存在两条边不相交的路径可以从点u出发到点v Input
第一行三个整数n,m,q 接下来m行,每行两个整数u,v,表示u和v之间有一条边 接下来q行,每行一个大写字母o和2个整数u、v,依次表示按顺序发生的q个事件: 当o为’Z’时,表示删除一条u和v之间的边 当o为’P’时,表示询问是否存在两条边不相交的路径可以从点u出发到点v Output
对于每组询问,如果存在,输出Yes,否则输出No Sample Input
7 8 7 1 2 1 3 1 4 2 3 3 4 3 7 7 4 5 6 Z 1 4 P 1 3 P 2 4 Z 1 3 P 1 3 Z 6 5 P 5 6 Sample Output
Yes Yes No No HINT
对于全部数据,max(n,m,q)<=100000 删边 不好做 改为离线 变成加边 然后动态维护边双联通分量即可
#include
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
暂时没有评论,来抢沙发吧~