问题描述
给定一个二维矩阵，表示网络中的各个节点的连通性，graph[i][j] = 1 表示 i 和 j 是连通的，graph[i][j] = 0 表示 i、j 不连通。给定一个 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);
}
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);
}
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;
}
}
|