题目大意:一个无向图需要确定一些安全出口,如果保证某个点断开后,其他各个点都能够找到安全出口?最少需要多少个出口?有多少种方案?
题目描述
原题来自:HNOI 2012
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。
请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。
输入
输入文件有若干组数据,每组数据的第一行是一个正整数 N,表示工地的隧道数,接下来的 N 行每行是用空格隔开的两个整数 S 和 T ,表示挖煤点 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。
输出
输入文件中有多少组数据,输出文件中就有多少行。每行对应一组输入数据的结果。
其中第 i 行以 Case i:
开始(注意大小写,Case
与 i
之间有空格,i
与 :
之间无空格,:
之后有空格),其后是用空格隔开的两个正整数,第一个正整数表示对于第 i 组输入数据至少需要设置几个救援出口,第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总数。
输出格式参照以下输入输出样例。
提示
样例输入
9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0
样例输出
Case 1: 2 4
Case 2: 4 1
样例解释
Case 1
的四组解分别是 (2,4),(3,4),(4,5),(4,6);
Case 2
的一组解为 (4,5,6,7)。
N≤500,输入数据保证答案小于 264。
解题思路
对于双连通分量,任意一个点断开后,其他点都是连通的,所以只需要随便选两个点即可。
但给定的图,不一定是双连通分量,可能有割点,如果有割点,我们只需要在叶子处设置1个安全出口即可,这样不管哪个点出问题(即使是割点),都可以往另外一个方向逃生。
最后是方案数,双连通分量中,除去割点以外的点都可以选择,分步用乘法原理即可。
细节:如何判断是叶子节点?
只遇到1个割点的双连通分量!每次Flood Fill一个点,遇到割点停下来,边搜索边统计遇到的普通点数量和割点数量,避免每次memset可以用时间戳,注意与初始值不能重合。
当然,也可以用Tarjan缩点,直接把双连通分量存储起来,不需要二次搜索。
需要提醒的是:数据提高的可以是非连通图,每个子图的方案需要累乘,选的点数量需要累加。