Advertisement

AcWing 1183. 电力 解析(双连通分量与割点)

阅读量:

AcWing 1183. 电力

复制代码
    1 统计连通块个数cnt
    2 枚举从哪个块j中删
1 从块j中删除哪个点i
2 删除点i后块j分成s部分(在样例3中删2后s=0)
      总共分成的部分 = s(i新的子块的个数)+cnt(删前总的连通块数)-1(删前子块的个数)
                     = 当前块的部分(s)+剩余连通块的数量(cnt-1)
                     = 1+1-1 (样例1:删2后 s=1 cnt=1 -1 =1
                     = 1+2-1 (样例2:删1后 s=1 cnt=2 -1 =2
                     = max(1+2-1,0+2-1)(样例3:删1后 s=1 cnt=2 -1=2 
                                              删2后 s=0 cnt=2 -1=1(点2所在的块删除2后没有点了 s=0)
                    dfn(x)<=low(y)
                    x删掉后y单独出来--多一个单独子树
                    如果x非

全部评论 (0)

还没有任何评论哟~