关于 DAG 的一个问题
  • 板块灌水区
  • 楼主xiejinhao
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/7/1 12:22
  • 上次更新2023/11/6 23:50:18
查看原帖
关于 DAG 的一个问题
196649
xiejinhao楼主2020/7/1 12:22
  • 对于 nnmm 边的 DAG\rm DAG,给出 qq 个询问 (x,y)(x,y) 表示询问 xx 是否存在到达 yy 的路径。

  • 0<n,m,q2×1030<n,m,q≤2×10^3

我们知道可以用 O(nq)O(nq) 的时间暴力解决这个问题。

所以改变一些条件:0<n,m,q1060<n,m,q≤10^6

问:能否在线性时间内做出所有判断呢?

2020/7/1 12:22
加载中...