05 Apr 10 WHU2010校赛预赛G题：Pseudoforest

题目大意：给一个图，求这个图的最大伪森林生成树。所谓的伪森林就是图中的任意两个圈都没有公共部分。

这题是我出的，这里说一下做法：从大到小排个序之后用类似Kruskal算法的并查集操作求得答案。对于已经有环的部分，需要做一个标记。

有一个很容易想到的但是是错误的做法：先求最大生成树，然后在每一个联通块里面添加最大边。对于这种数据，这种做法是明显错误的。

A—B—-C—D（AB, BC, CD分别连接）

A–E–B C–F–D （AE, EB, CF, FD连接）

如果先求得最大生成树，那么最终答案一定有B-C这条边。

但是事实上，我们很容易构造边权，使得ABC和CDF分别连通来构成最大伪森林。（这样就不包含B-C这条边了)

Filed in Iproblem