Tarjan+LCA

HDU 2460 Network

题意: 给定一个无向图，然后给出q个加边操作，询问每次加边后图中桥边的个数。

这题根本不会欸，去网上搜题解，用到的算法也是一大堆，好多都是没学过的。然后就去看蓝书，用Tarjan算法求桥边。下面是求解桥边的算法

• 时间戳: 图的深度优先遍历，每个节点第一次被访问的时间顺序，用$dfn[i]$表示
• 搜索树: 图的深度优先搜索构成了一棵搜索树(不连通的图构成搜索森林)
• 追溯值: Tarjan算法引入一个追溯值$low[x]$，设$subtree(x)$表示搜索树中以x为根的子树. $low[x]$定义如下
  • $subtree(x)$ 中的节点