这是一个创建于 1257 天前的主题，其中的信息可能已经有所发展或是发生改变。
有两种表达式
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),是否有更优的算法?
 |
1
YetToCome 2021-05-29 17:17:20 +08:00 via Android
双指针
|
 |
2
geelaw 2021-05-29 17:43:42 +08:00 via iPhone  2
Tarjan 算法正是你所需要的。
第二个问题很容易解答，有一个明显的 nlogn 算法，但是否可以降低到 n 我就懒得想了，可以试着找找强连通分量的在线算法。 |
 |
3
lance6716 2021-05-29 19:22:22 +08:00 via Android
[A >= B, B >= A] 是一个有向无环图, 其中 A 和 B 被视为同一个点
当即可以解释为是，又可以解释为不是，要以”是有向无环图“优先 |
 |
4
akira 2021-05-29 19:54:15 +08:00
[A > B, B >= A] 这个怎么理解，A B 是不是同一个点
|
 |
5
aguesuka OP @akira 这种情况 A 和 B 不是同一个点, 所以 A > B > A 构成一个环. 可以把 A 和 B 看作类型为自然数的变量, `>=` 是大与小于, `>`是大于, 判断是否存在整数, 带入情况, 满足条件.
|
|
6
aguesuka OP @geelaw 就是这个算法. 第二个问题, 二分法可以做到 O(n log n) , 我想的是在对问题一做了算法的判定以后, 在数组后追加一个表达式, 有没有小于线性时间的算法. 不过 strongly connected components algorithm 这个关键字已经足够了.
|
 |
7
sillydaddy 2021-05-30 08:47:14 +08:00 1
楼主的这个>, >=的抽象好简洁。能问一下是从什么里面抽象出来的问题啊？
开始我想的方法，就是逐渐添加表达式，然后判断每一次添加，是否会造成环(所以对楼主的第二个问题感到奇怪)。然后发现每次添加新表达式后，总是要做一个“判断某个点是不是另一个点的父点”的操作，涉及到了查表。而查表的复杂度是 O(m)(m 是点的个数)，导致最后复杂度是 O(n*m)。看到 @geelaw 提到的 Tarjan 算法，发现它巧妙的用动态构建的栈将这个查表的复杂度降到了 O(1)，然而动态构建栈的代价是，建栈必须考虑整个图的所有连接信息，而如果是依次添加列表项，连接信息不完整，栈的方法就无效了。Tarjan 方法似乎和逐次添加列表项的方法是矛盾的。 不知道楼主第 2 个问题的复杂度是多少，感觉降到了 O((n+m)log(n))已经是挺神奇了。 |
|
8
aguesuka OP @sillydaddy 类型论中的隐式 Universe level 推导, 第二个问题其实就是完成某个函数的推导以后, 另一个调用其的函数是否能利用推导的结果. 理想是线性的, 现在看来不大可能, 也许需要找下相关源码或者 paper 看它们是怎么实现的.
|
Select Language