leetCode-924:Minimize Malware Spread

问题描述

给定一个二维矩阵,表示网络中的各个节点的连通性,graph[i][j] = 1 表示 ij 是连通的,graph[i][j] = 0 表示 ij 不连通。给定一个 initial 数组,数组元素表示网络中被病毒感染的节点,病毒感染具有传播性。要求从 initial 数组中删除某个节点,使网络中被病毒感染的节点数最少。如果存在多个节点,则返回数字最小的节点。题目链接:点我

样例输入输出

输入:graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]

输出:0

输入:graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]

输出:1

问题解法

使用并查集算法,找出网络中有多少个隔离的集群,分别计算每个集群中的节点数。遍历 initial 数组,剔除同一个集群下的元素,对剩下的元素,分别获取其所在集群的节点数,取其最大值,此时对应的元素就是要剔除的节点。代码如下

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
class Solution
{
public int minMalwareSpread(int[][] graph, int[] initial)
{
// 初始化
int[] parents = new int[graph.length];
for (int i = 0; i < parents.length; i++)
{
parents[i] = i;
}

// 使用并查集找出网络中隔离的集群
for (int i = 0; i < graph.length; i++)
{
for (int j = 0; j < i; j++)
{
if (graph[i][j] == 1)
{
int iParent = findParent(parents, i);
int jParent = findParent(parents, j);
if (iParent != jParent)
{
parents[iParent] = jParent;
}
}
}
}

// 计算网络中隔离的集群每个集群的节点数
Map<Integer, Integer> childrenCountMap = new HashMap<>();
for (int i = 0; i < parents.length; i++)
{
int root = findParent(parents, parents[i]);
childrenCountMap.put(root, childrenCountMap.getOrDefault(root, 0) + 1);

}

// 找出 initial 中处于同个集群的节点
Map<Integer, Integer> duplicateMap = new HashMap<>();
for (int i = 0; i < initial.length; i++)
{
int root = findParent(parents, initial[i]);
duplicateMap.put(root, duplicateMap.getOrDefault(root, 0) + 1);
}

// 找出 initial 中元素所在的集群中拥有最多节点数的集群
Arrays.sort(initial);
int node = initial[0];
int maxNum = -1;
for (int i = 0; i < initial.length; i++)
{
int root = findParent(parents, initial[i]);
if (duplicateMap.get(root) == 1 && childrenCountMap.get(root) > maxNum)
{
maxNum = childrenCountMap.get(root);
node = initial[i];
}
}

return node;
}

private int findParent(int[] parents, int i)
{
while (parents[i] != i)
{
i = parents[i];
}

return i;
}
}