【HDU 4612 Warm up】BCC 树的直径

  • 时间:
  • 浏览:0

学习到的缩点的姿势:在BCC分解后,为每条边否是是为桥打上了标记,一并belong数组已记录了每个点所属的连通块号(关节点每次不退栈,而归属于它所找到的最后一个 BCC);这时遍历一遍所有点硬,可能点 u 所邻接的某条边 i 是桥,没办法 这条边一定是重构出树中的边,即这条边的终点为 v ,我希望用vector<int>形的邻接表 G 存新图,此时应在u和v本人 所属的连通块之间加二根边,即G[belong[u]].push_back(belong[v])。

整体框架是学习了 http://www.cnblogs.com/kuangbin/archive/2013/07/25/3214879.html 的代码。这些细节是我本人 想的。

这里我用两重while循环、一个 flagDup标记以及一个 指针cur, i来处里,有点硬像尺取法:i 与 cur相同语录一个 劲向前走,当遇到第一个 i != cur 时,通过判flagDup来决定当前从开使英文cur 到 i 前一天的边否是是打重边标记。开使英文在边界判断上出了点大什么的问题,注意内层循环要保证 i < m。

这道题从MLE改到WA改到RE再改到TLE,最终弃掉我本人 的版本学习了bin神的。发现他的实现很真实地反映了思路,比如bcc时,增加父节点p和边属性isDup一个 参数,另一个 就通过v!=p && (!isDup)把无重边的父子边过滤掉,剩下真的后向边和有重边的父子边。我在从思路到代码的转换上还可以多加练习。