Sunday, October 28, 2018

[LeetCode] Minimize Malware Spread


对于这道题,我们需要明确几点:

  1. 如果initial list中的某些节点是其所在component唯一在initial list中的节点的话,如果其所在的component越大,那么将其从initial list remove之后能够减少的感染节点越多。
  2. 如果不存在上述的节点,证明每一个component都有至少两个节点在initial list中,那么remove任何一个节点都不会减少被感染的节点数,所以return 0
所以我们只需要dfs寻找满足条件1的所在component最大的节点。如果不存在返回0。时间复杂度O(V + E),代码如下:


No comments:

Post a Comment