[POJ 3694] 双连通分量、lca、tarjan、缩环

【题目大意】给定一个无向连通图,每次操作是在原图上加一条边,对于每次操作,输出剩下多少桥。

【算法分析】

什么是桥?就是去掉这条边以后图不再连通了。

试想一下如果缩环以后会把这个图弄成一棵树会怎样呢?

那就是树中的每条边都是割边(环上的不可能是割边)。

于是我们可以先用tarjan缩点,然后建起这颗树来。

每次如果添加边的话,那么就找那两个点对应的点的lca。

然后找lca路径上的点都缩到lca上去。

这样每条边只会常数次。所以总时间复杂度为O(E)。

【HINT】一开始SB了,想了很久,以为要把边做一下调整,后来才发现根本不用,因为树中的边肯定不可能是重边,否则那两个点都已经合成一个了。。。

【其他】居然1A,真不敢相信

纪念一下,刚好10000K内存。。。我保证,我只交了一次。。。而且没算过内存。。。

6324346 edward2 3694 Accepted 10000K 422MS C++ 2731B 2010-01-09 23:48:06

【程序】

#include

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注