LeetCode 928 Minimize Malware Spread II | ReeeStart

LeetCode 928 Minimize Malware Spread II | ReeeStart

这题和Minimize Malware Spread I的区别是:

I: 问如果从initial中取掉一个server, 把这个server的病毒给清了, 那要对哪个server杀毒, 能使得最终Internet里被感染的结点数最少?
II: 问如果从Initial中取掉一个server, 把它从整个网络中拿掉, 要拿掉哪个server, 能使最终被感染的结点数最少?

#Solution

#Solution #1 - Union Find - Without Optimization

最简单的就是重头做N遍union-find, 每次取掉initial中的一个server. 然后每次求中毒的数量.

Time: O(N * NlogN)

#Solution #2 - Union Find Optimization

第二种解法是对上一个方法的优化, 通过观察我们可以得到, 因为只能取掉一个server:

• 如果排除initials再union-find之后的某个component, 不包含任何initials, 则不受影响.
• 如果排除initials再union-find之后的某个component, 只包含一个中毒server, 那么取掉这个中毒的可以使这个component不受影响.
• 如果排除initials再union-find之后的某个component， 包含多个中毒servers, 那么取掉谁都一样. 该中毒的还是要中毒.

所以我们最终的答案, 肯定是在那些只包含一个中毒server的component里面找.

Read full article from LeetCode 928 Minimize Malware Spread II | ReeeStart