在亚马逊的一次采访中，人们是如何应对这个挑战的？

Question

我正在努力优化这个亚马逊过去的采访问题，其中涉及一个DAG。

这就是我试过的(代码很长，我宁愿解释)-

1. 基本上，因为这个图是一个DAG，而且由于它是一个传递关系，所以对每个节点进行简单的遍历就足够了。
2. 因此，对于每一个节点，我会通过传递性遍历所有的可能性，得到端点，然后比较这些端点，得到最有噪音的人。
3. 在我的第二步中，我实际上找到了第二步中遍历的所有顶点中最嘈杂的一个人(也许是唯一的一个)，所以我在映射中回忆了所有这些，并标记了遍历的顶点。
4. 因此，我基本上为图维护了一个邻接列表，一个访问/非访问映射和一个输出映射(每个顶点的噪声最大的人)。
5. 这样，当我得到一个查询时，我将不必重新计算任何内容(在重复查询的情况下)。

上面的代码可以工作，但是由于我不能用测试用例进行测试，所以它可能/不可能超过时间限制。是否有更快的解决方案(可能使用DP)。我觉得我还没有充分利用传递性和反对对称性的条件。

显然，我并不是在调查一个人比现在的人更不富有的情况。但是，例如，如果我有- (1,2)(1,3)(1,4)...etc和可能(2,6)(2,7)(7,8)等对，那么如果给我找到一个比1更富有的人，我会遍历每一个1的邻居，然后每个邻居的邻居也会。这只在我存储结果时完成一次。

问题1

问题2

编辑(增加问题文本)-

鲁纳克今年就要毕业了。他会发财的。非常富有。如此富有，以至于他决定有一种结构化的方法来衡量他的丰富程度。因此，他在城里四处询问人们他们的财富，并记下这些信息。Rounaq指出，如果习比易拥有更多的财富的话，这对夫妻就会被记录下来。他还记下了每个人的安静程度。Rounaq认为，吵闹的人是一种滋扰。因此，对于他的每一个朋友艾，他想确定谁是最吵闹(最不安静)的人谁拥有比艾多。请注意，“拥有比”更多的财富是一种传递性和反对称关系。因此，如果a比b有更多的财富，b比c更有财富，那么a比c有更多的财富，而且如果a比b的财富更多，那么b的财富就不可能超过a，你在这个问题上的任务是帮助Rounaq根据Rounaq从镇上收集到的信息，帮助Rounaq确定在他的每个朋友ai中最吵闹的人。输入第一行包含T:每个测试用例的测试用例数有以下格式：

N

K1 K2 K3 K4：：Kn

我

X1 Y1

X2 Y2

。。。

。。。

问：

A1

A2

。。。

。。。

AQ

N:城里的人数

M: Rounaq能够获得财富信息的对数

问:Rounaq的朋友数

Ki:人的安静程度

易:这对Rounaq记下了(一对独特的价值观)。

艾:Rounaq的朋友

对于每个Rounaq的朋友，打印一个整数--根据要求，最吵闹的人的安静程度，或者-1，如果没有比这位朋友更富有的人。

Answer 1

对对拓扑排序执行X，Y。然后从最富有的人到最不富有的人，并储存到目前为止最吵闹的人：

less wealthy    ->    most wealthy
<- person with lowest K so far <-

然后，对于每个查询，二进制搜索的第一个人比朋友更富有。我们储存的价值是最吵闹的人，比朋友更富有。

更新

似乎我们不能依赖于允许一个完整的拓扑排序的数据。在这种情况下，遍历图的部分，从已知的最大到最少的财富，存储为每个人访问最嘈杂的人到目前为止。您提供的示例可能如下所示：

  3 - 5
 /    |
1 - 2 |
   /  |
  4 --

横穿：

1 <- 3 <- 5
1 <- 2
4 <- 2
4 <- 5

(输入)

2 1
2 4
3 1
5 3
5 4
8 2 16 26 16

(查询和解决方案)

 3  4  3  5  5 
16  2 16 -1 -1