请教个有向图的算法题

[aguesuka]

有两种表达式

• A > B 代表有向图中, 点A可以到达点B, 而且两者不能是同一个点.
• A >= B 代表有向图中, 点A可以到达点B, 或者两者是同一个点.

输入表达式的列表, 判断是否满足有向无环图的条件:

如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图

例如

• [A > B, B > C] 是一个有向无环图
• [A >= B, B >= A] 是一个有向无环图, 其中 A 和 B 被视为同一个点
• [A > B, B >= A] 不是一个有向无环图

直觉上有 O(n) 的算法.
推广: 假设列表的前 x 项可以构成有向无环图,那么 x 的最大值是多少?
如果第一个问题有 O(n) 的算法, 那么第二个问题可以使用第一个算法做遍历,时间复杂度是 O(n * n),是否有更优的算法?

[YetToCome]

双指针

[geelaw]

Tarjan 算法正是你所需要的。

第二个问题很容易解答，有一个明显的 nlogn 算法，但是否可以降低到 n 我就懒得想了，可以试着找找强连通分量的在线算法。

[lance6716]

[A >= B, B >= A] 是一个有向无环图, 其中 A 和 B 被视为同一个点

当即可以解释为是，又可以解释为不是，要以”是有向无环图“优先

[akira]

[A > B, B >= A] 这个怎么理解，A B 是不是同一个点

[aguesuka]

@akira 这种情况 A 和 B 不是同一个点, 所以 A > B > A 构成一个环. 可以把 A 和 B 看作类型为自然数的变量, `>=` 是大与小于, `>`是大于, 判断是否存在整数, 带入情况, 满足条件.

[aguesuka]

@geelaw 就是这个算法. 第二个问题, 二分法可以做到 O(n log n) , 我想的是在对问题一做了算法的判定以后, 在数组后追加一个表达式, 有没有小于线性时间的算法. 不过 strongly connected components algorithm 这个关键字已经足够了.

[sillydaddy]

楼主的这个>, >=的抽象好简洁。能问一下是从什么里面抽象出来的问题啊？

开始我想的方法，就是逐渐添加表达式，然后判断每一次添加，是否会造成环(所以对楼主的第二个问题感到奇怪)。然后发现每次添加新表达式后，总是要做一个“判断某个点是不是另一个点的父点”的操作，涉及到了查表。而查表的复杂度是 O(m)(m 是点的个数)，导致最后复杂度是 O(n*m)。看到 @geelaw 提到的 Tarjan 算法，发现它巧妙的用动态构建的栈将这个查表的复杂度降到了 O(1)，然而动态构建栈的代价是，建栈必须考虑整个图的所有连接信息，而如果是依次添加列表项，连接信息不完整，栈的方法就无效了。Tarjan 方法似乎和逐次添加列表项的方法是矛盾的。

不知道楼主第 2 个问题的复杂度是多少，感觉降到了 O((n+m)log(n))已经是挺神奇了。

[aguesuka]

@sillydaddy 类型论中的隐式 Universe level 推导, 第二个问题其实就是完成某个函数的推导以后, 另一个调用其的函数是否能利用推导的结果. 理想是线性的, 现在看来不大可能, 也许需要找下相关源码或者 paper 看它们是怎么实现的.