在图论中有k连通的定义

最少删掉k个点， 使得图不连通的话， 那个这个图被称为k连通。

1连通就是看看是不是直接连通

2连通就是看看图中是不是有关节点啦（有关节点就是1连通或0连通）

很明显这个题目中给的图就是看是不是一个3连通4连通5连通……

做法嘛。。。可以直接根据定义， 来枚举两个点， 看看删掉两点之后是不是还是连通的。（如果不连通的话， 那么根据定义， 就不可能是3连通了， 更不可能是4连通了）

但是这样会tle， 所优化一点就可以了。

具体做法就是楼上说的。

不过求桥是没有必要的， 只要求是不是有关节点就可以了

因为删掉一个点之后还存在关节点的话， 那么也就是说只要删掉这两个点， 这个图就不连通了。
也就是说这个图顶多是一个2连通。（不可能是3or4连通）

• 强 佩服 用你的理论我一次AC (0) Bzin 2009-05-06 15:59:23