P2272 [ZJOI2007]最大半连通子图 题解

本题解相对于其他题解的特色有二： 一、深入分析了为什么要去重 二、给出了链式前项星的 O(m)O(m)O(m) 线性去重方式 下面进入正文。 不难发现，将原图缩点成一个DAG后，图中的每一条链都是一个半连通子图，而最长的链就是最大半连通子图。 注意：新图中一个点的权值为这个点代表的SCC的点数，一个链的长度为各点权值之和。 统计最长链的权值不难，可以使用拓扑排序或记搜实现。为了避免引入STL影响效率，本文统一使用记搜。 本题的难点在统计方案数。 统计最小生成树方案数、最短路方案数等经典题的解法会给我们启示，紧紧抓住三角不等式这一核心算式，不断更新答案并继承方案数，这种方法依然使用本题。 但有所不同的是，本题需要考虑重边。 认真思考不难发现，传统的 tarjan 缩点得到的DAG中会出现重边（这里的重边是..