在通信计算机网络中计算被恶意软件感染的计算机集？

Question

一点背景故事：自从我用 C 编写代码以来已经有很长时间了（一年。跳回到这里真的让人不知所措。

我需要一些关于实施的建议。 有人可以解释一下您将如何设计这个吗？我理解问题的概念，但对如何开始实施感到迷茫。

约束条件如下：

输入（给算法）：

1. 网络中计算机的数量，指定为N。假设计算机被命名为1、2..直到N。

2. 由三元组列表 (C1, C2, t) 组成的日志。在每个三元组中，C1 和 C2 是计算机名称，t 是时间戳。如果（C1，C2，t）出现在日志中，则说明C1和C2在时间t进行了通信。 （t 始终是 >= 到 0 的整数）

3. 有一台计算机，CBad，这是首次引入恶意软件的计算机的名称。还有一个时间戳 tBad，它是恶意软件被引入 CBad 的时间。

感染机制：

1. 如果一台计算机（例如 C0）被感染，而另一台计算机 C1 在时间 t 与 C0 通信，则 C 也会被感染。 （它会在时间t被感染。）

2. 如果一台计算机在时间t被感染，那么它在任何时间t1>=t被感染（换句话说，它被认为在那个时间点和之后的任何时间被感染）

这里的预期输出是一个 txt 文件，显示由于 CBad（我们的患者 0）在时间 tBad 被感染而导致的受感染计算机列表。

我们一直在讨论最小生成树算法（特别是 Prims 和 Kruskals）我很确定他想使用其中之一来解决这个问题。

到目前为止的想法： 到目前为止，我的理论是在每个三元组列表中，C1 和 C2 代表构成一条边的两个顶点。时间戳 t 表示该边缘的 cost/weight/whatever。我必须以某种方式构建一个连接的无向图，然后 运行（Kruskal 算法？）才能找到集合？...我只是不知道。我觉得自己像个白痴。 :(

Answer 1

你想多了。虽然可以将场景的一部分表示为有向图，但这种表示似乎并不适合此处进行任何有用的优化。 （特别是因为 t 不代表任何具有类似权重行为的东西。）相反，考虑一种直接的方法：

• 初始化一组节点 S（代表 "infected" 台计算机）以仅包含 CBad。
• 从您的列表中删除所有具有 t < tBad.
的三元组
• 将剩余的三元组按 t 排序。
• 对于新排序列表中的每个三元组 (C1, C2, t)：
  • 如果 C1 在 S 中，将 C2 添加到 S。
• Return S.
的内容

这是 O(n log n)，因为我们必须对列表进行排序。可能有一些聪明的方法可以做到这一点 O(n)，但我有点怀疑。