求助两个关于 DAG 的问题
  • 板块学术版
  • 楼主b6e0_
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/8/2 09:50
  • 上次更新2023/10/27 17:25:19
查看原帖
求助两个关于 DAG 的问题
150522
b6e0_楼主2022/8/2 09:50

nn 个点 mm 条边的 DAG:

  1. qq 次查询 xx 是否能到达 yy
  2. 对于每个点 xx,求有多少点能到达 xx

n,m,qn,m,q 同阶。

看起来很经典的样子,但是没搜到

求助是否有比 O(n2w)\mathcal O(\frac{n^2}w) 快的算法?

2022/8/2 09:50
加载中...