【HDU 4612 Warm up】BCC 树的直径

  • 时间:
  • 浏览:0
  • 来源:uu快3开奖_uu快3娱乐_输钱

整体框架是学习了 http://www.cnblogs.com/kuangbin/archive/2013/07/25/3214879.html 的代码。许多细节是每个人想的。

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

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

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