有两种表达式
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 看它们是怎么实现的.
|