MENU

HDU 2460 Network

2019-06-29 • 阅读: 21 • 阅读设置

Tarjan+LCA

HDU 2460 Network

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

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

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

返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码