n个电脑间连着网线, 保证连通, 无向, 现在添加q条网线, 可重边, 问每次还剩多少桥.

这题只要将桥求出来, 然后缩点, 再LCA即可, 我之前缩点之后写成了DFS, 超级麻烦还WA.
其实也不用缩点, 在求桥的时候把每个节点的深度dep和父节点pre记录下来即可, 这样在
LCA中可以利用这些信息先使两个点上升至同一深度, 然后再一起上升, 直到两点重合, 期
间遇到桥就将桥的标记删去, 然后ans减1即可.

注意这里求桥的方法, 感觉刘汝佳的黑书上的方法较为繁琐, 还要判断是不是根, 这里用算
法导论上的公式:

low(u)=min{dfn(u), min{low(w)|w是u的儿子}, min{dfn(w)|(u,w) 是一条后向边}}
low(u)表示从u出发, 经过一条其后代组成的路径和后向边, 所能到达的最小深度的顶点的
编号. dfn(u)是深搜过程中对顶点的编号值.

割点是dfn[u]>=low[v], 桥是dfn[u]>low[v].
这里特别注意桥的表示, 可以把边存下来, 也可以把离根远的节点编号存下来(如果根只有
一个的话). 并且如果存节点, 则存的是v, 而在求割点时存的是u.

针对这题还有两个地方注意, 一是不判重边也可以AC(判的话就把重边存下来, 然后当作后
面的输入来处理), 二是记得各数组的初始化, 奇怪的是用来存图的邻接表我忘记清空了竟
然也AC...

• 为什么 不用 判重边呢````晕```那 这个数据呢 (67) __sunshine 2009-09-11 08:57:13
  • Thank you for your test (0) shuaige123 2013-03-11 16:47:35