Interactive Graph Search

oxx1108 edited 4 年,3 月前

问题:
交互题,给一棵有根树 / DAG,需要找到一个目标结点 t。每次可以 query 一个结点 q,系统会返回是否存在一条 path 从 q 到 t。

链的时候直接二分就行。
树的时候树剖之后链上二分,对于儿子来说优先 query 结点个数总和多的子树。
DAG 上提取出 heavy DFS tree(按重边顺序DFS),在上面可以和 tree 一样做。(可以证明正确性,这个是唯一精妙的地方)

Research ideas:
For k targets?
Limit the number of query?

Problem ideas:
1. 每次返回目标点到查询结点的距离
2. 每次返回目标点是否在查询点的 k 步范围内

Past Versions

Comments