#题目描述

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。

#做法

这是图论

我开始看到\(N\le 500\)这个条件吓尿了，这是爆搜的节奏啊

然后发现用求割点是可做的

首先求出割点，然后缩图

这样找出仅和一个割点联通的块的个数

然后乘法原理跑一下就够了

#复杂度分析

用Tarjan算法求割点的时间复杂度为\(O(n)\)

各种处理均摊大概是\(O(N \sqrt{N})\)