#Problem

#⭐️⭐️⭐️⭐️⭐️

这题和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里面找.

Time: O(N^2 )

#Code

#Solution #1 - Union Find without optimization - Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
public int minMalwareSpread(int[][] graph, int[] initial) {
int n = graph.length;
int infects = Integer.MAX_VALUE;
int res = -1;
Arrays.sort(initial);
for (int bad : initial) {
int[] roots = new int[n];
int[] size = new int[n];
for (int i = 0; i < n; i++) {
roots[i] = i;
size[i] = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && i != bad && j != bad && graph[i][j] == 1) {
if (root(roots, i) != root(roots, j)) {
union(roots, size, i, j);
}
}
}
}
int totalInfects = 0;
int[] visited = new int[n];
for (int x : initial) {
if (x != bad) {
int r = root(roots, x);
if (visited[r] != 1) {
totalInfects += size[r];
visited[r] = 1;
}
}
}
if (totalInfects < infects) {
infects = totalInfects;
res = bad;
}
}
return res;
}
private int root(int[] roots, int i) {
while (i != roots[i]) {
roots[i] = roots[roots[i]];
i = roots[i];
}
return i;
}
private void union(int[] roots, int[] size, int i, int j) {
int r1 = root(roots, i);
int r2 = root(roots, j);
if (size[r1] < size[r2]) {
roots[r1] = r2;
size[r2] += size[r1];
} else {
roots[r2] = r1;
size[r1] += size[r2];
}
}
}
#Solution #2 - Union Find with Optimization
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
public int minMalwareSpread(int[][] graph, int[] initial) {
int n = graph.length;
Set<Integer> malwares = new HashSet<>();
for (int bad : initial) malwares.add(bad);
int[] roots = new int[n];
int[] size = new int[n];
for (int i = 0; i < n; i++) {
roots[i] = i;
size[i] = 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && !malwares.contains(i) && !malwares.contains(j) && root(roots, i) != root(roots, j) && graph[i][j] == 1) {
union(roots, size, i, j);
}
}
}
Arrays.sort(initial);
Map<Integer, Set<Integer>> componentWithMalware = new HashMap<>();
for (int bad : initial) {
for (int i = 0; i < n; i++) {
if (!malwares.contains(i) && graph[i][bad] == 1) {
int r = root(roots, i);
componentWithMalware.putIfAbsent(r, new HashSet<>());
componentWithMalware.get(r).add(bad);
}
}
}
int infects = -1;
int res = initial[0];
for (int r : componentWithMalware.keySet()) {
if (componentWithMalware.get(r).size() == 1) {
int v = componentWithMalware.get(r).iterator().next();
if (size[r] > infects) {
infects = size[r];
res = v;
} else if (size[r] == infects && v < res) {
res = v;
}
}
}
return res;
}
private int root(int[] roots, int i) {
while (i != roots[i]) {
roots[i] = roots[roots[i]];
i = roots[i];
}
return i;
}
private void union(int[] roots, int[] size, int i, int j) {
int r1 = root(roots, i);
int r2 = root(roots, j);
if (size[r1] < size[r2]) {
roots[r1] = r2;
size[r2] += size[r1];
} else {
roots[r2] = r1;
size[r1] += size[r2];
}
}
}

Comments