【泉七培训-刘定峰】链型网络

2014年12月26日1,3880

题意

给定一张无重边,自环的无向图

每次可以加边,或者询问有多少个点满足将该点删除后,原图的每个连通块都为一条链

 

数据范围

30%的数据n<=100 m<=2n

100%的数据n<=100000,m<=2n

 

题解

30分很简单

对于每次询问枚举删去每一个点,然后再用O(n)的时间在图上判环以及度数是否都小等于2

 

然后正解。。。

考虑以下一些简单的情况

原图为若干条链,则答案为点数N

原图为单个简单环加若干条链,则答案为环大小

原图中超过一个连通块有环,答案为0

原图中一个连通块为一个点连接三条链,答案为4,三棵树不是很容易确定

原图中一个连通块为一个点连接三条以上的链,答案为1

另外显然随着边的加入,答案不会增大

考虑链的性质,一个图的每个连通块为链,等价于每个点的度数小于等于2且无环

考虑图中如果存在一个度数大于等于3的点u, 因为要保证去掉一个点后每个点的度数都小于等于2,我们要么去掉u,要么在u度数恰好为3时,去掉u 的三个相邻点中的一个,而其他的点均不可能成为答案

这样我们只需要在加边过程中第一次出现度数为3的点的时候, 对于可能成为答案的4个点,分别维护一个去掉该点之后的图,然后询问在4个图中分别进行判断,若某个图中无环且无度数>=3的点,即图中连通块均为链,则ans++

实现只要用个带权并查集

30分

100分