有向图定点对动态连通性
  • 板块学术版
  • 楼主AuKr
  • 当前回复18
  • 已保存回复18
  • 发布时间2020/10/28 20:03
  • 上次更新2023/11/5 09:39:15
查看原帖
有向图定点对动态连通性
317568
AuKr楼主2020/10/28 20:03

给一张有向图(开始为空),和上面任意点对 (x,y)(x,y)。(一直不变)

有两种操作:

u,vu,v 之间加一条有向边;

询问给出的点对是否连通。

连通指从 存在至少一条 x>yx->y 的路径。

求最坏复杂度在 O(nm)\mathcal O(nm) 以下的做法

2020/10/28 20:03
加载中...