0924-尽量减少恶意软件的传播

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1
时，表示节点 i 能够直接连接到另一个节点 j。

一些节点 initial
最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

如果从 initial 中 移除某一节点 能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回 索引最小
的节点。

请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。

示例 1：

**输入：** graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
**输出：** 0

示例 2：

**输入：** graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
**输出：** 0

示例 3：

**输入：** graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
**输出：** 1

提示：

  • n == graph.length
  • n == graph[i].length
  • 2 <= n <= 300
  • graph[i][j] == 0 或 1.
  • graph[i][j] == graph[j][i]
  • graph[i][i] == 1
  • 1 <= initial.length <= n
  • 0 <= initial[i] <= n - 1
  • initial 中所有整数均 不重复

方法一： 深度优先搜索

思路

首先，把图中所有的连通分量各自标上不同的颜色，这可以用深度优先搜索来实现。

如题所述，如果 initial 中的两个节点的颜色相同（即属于同一个连通分量），那移除这种节点是不会减少 M(initial) 的，因为恶意软件会感染同一个连通分量中的所有节点。

因此，对于 initial 中颜色唯一的节点，从中选择一个移除来最大限度地减少被感染节点数。(如果有多个节点都可以达成最优解，就选择下标最小的节点。另外，如果没有颜色唯一的节点，就直接返回下标最小的节点。)

算法

算法包括以下几个部分：

  • 给连通分量上色： 遍历每个节点，如果它还没有颜色，就用深度优先搜索去遍历它所在的连通分量，同时给这个连通分量标上新的颜色。

  • 计算每个连通分量的大小： 数一下每个颜色的节点各有多少个。

  • 找到唯一的颜色： 找到 initial 中颜色唯一的节点。

  • 选择答案： 对于 initial 中颜色唯一的节点，计算这个颜色节点的个数。从中选出最大节点个数的那个，如果有多个最优解，选择其中节点下标最小的。

  • 如果没有颜色唯一的节点，直接返回 min(initial)。

[solution1-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
class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        // 1. Color each component.
        // colors[node] = the color of this node.

        int N = graph.length;
        int[] colors = new int[N];
        Arrays.fill(colors, -1);
        int C = 0;

        for (int node = 0; node < N; ++node)
            if (colors[node] == -1)
                dfs(graph, colors, node, C++);

        // 2. Size of each color.
        int[] size = new int[C];
        for (int color: colors)
            size[color]++;

        // 3. Find unique colors.
        int[] colorCount = new int[C];
        for (int node: initial)
            colorCount[colors[node]]++;

        // 4. Answer
        int ans = Integer.MAX_VALUE;
        for (int node: initial) {
            int c = colors[node];
            if (colorCount[c] == 1) {
                if (ans == Integer.MAX_VALUE)
                    ans = node;
                else if (size[c] > size[colors[ans]])
                    ans = node;
                else if (size[c] == size[colors[ans]] && node < ans)
                    ans = node;
            }
        }

        if (ans == Integer.MAX_VALUE)
            for (int node: initial)
                ans = Math.min(ans, node);

        return ans;
    }

    public void dfs(int[][] graph, int[] colors, int node, int color) {
        colors[node] = color;
        for (int nei = 0; nei < graph.length; ++nei)
            if (graph[node][nei] == 1 && colors[nei] == -1)
                dfs(graph, colors, nei, color);
    }
}
[solution1-Python]
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
class Solution(object):
    def minMalwareSpread(self, graph, initial):
        # 1. Color each component.
        # colors[node] = the color of this node.

        N = len(graph)
        colors = {}
        c = 0

        def dfs(node, color):
            colors[node] = color
            for nei, adj in enumerate(graph[node]):
                if adj and nei not in colors:
                    dfs(nei, color)

        for node in xrange(N):
            if node not in colors:
                dfs(node, c)
                c += 1

        # 2. Size of each color.
        # size[color] = number of occurrences of this color.
        size = collections.Counter(colors.values())

        # 3. Find unique colors.
        color_count = collections.Counter()
        for node in initial:
            color_count[colors[node]] += 1

        # 4. Answer
        ans = float('inf')
        for x in initial:
            c = colors[x]
            if color_count[c] == 1:
                if ans == float('inf'):
                    ans = x
                elif size[c] > size[colors[ans]]:
                    ans = x
                elif size[c] == size[colors[ans]] and x < ans:
                    ans = x

        return ans if ans < float('inf') else min(initial)

复杂度分析

  • 事件复杂度： O(N^2)，其中 N 是 graph 的大小。

  • 空间复杂度： O(N)。

方法二： 并查集

思路和算法

同 方法一 一样，也得找出图中所有的连通分量，不同的是这一步用并查集来做。

在并查集中会额外计算连通分量的大小，当合并两个连通分量的时候，会把它们的大小进行累加。

借助并查集，可以用 方法一 中一样的思路处理：对于 initial 中每个颜色唯一的节点，都去计算连通分量的大小，从中找到最优解。如果 initial 中没有颜色唯一的节点，直接返回 min(initial)。

简洁起见，实现的并查集没有根据 rank 合并，这会让渐进复杂度变大一点。

[solution2-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;
        DSU dsu = new DSU(N);
        for (int i = 0; i < N; ++i)
            for (int j = i+1; j < N; ++j)
                if (graph[i][j] == 1)
                    dsu.union(i, j);

        int[] count = new int[N];
        for (int node: initial)
            count[dsu.find(node)]++;

        int ans = -1, ansSize = -1;
        for (int node: initial) {
            int root = dsu.find(node);
            if (count[root] == 1) {  // unique color
                int rootSize = dsu.size(root);
                if (rootSize > ansSize) {
                    ansSize = rootSize;
                    ans = node;
                } else if (rootSize == ansSize && node < ans) {
                    ansSize = rootSize;
                    ans = node;
                }
            }
        }

        if (ans == -1) {
            ans = Integer.MAX_VALUE;
            for (int node: initial)
                ans = Math.min(ans, node);
        }
        return ans;
    }
}


class DSU {
    int[] p, sz;

    DSU(int N) {
        p = new int[N];
        for (int x = 0; x < N; ++x)
            p[x] = x;

        sz = new int[N];
        Arrays.fill(sz, 1);
    }

    public int find(int x) {
        if (p[x] != x)
            p[x] = find(p[x]);
        return p[x];
    }

    public void union(int x, int y) {
        int xr = find(x);
        int yr = find(y);
        p[xr] = yr;
        sz[yr] += sz[xr];
    }

    public int size(int x) {
        return sz[find(x)];
    }
}
[solutino2-Python]
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
class DSU:
    def __init__(self, N):
        self.p = range(N)
        self.sz = [1] * N

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr
        self.sz[yr] += self.sz[xr]

    def size(self, x):
        return self.sz[self.find(x)]


class Solution(object):
    def minMalwareSpread(self, graph, initial):
        dsu = DSU(len(graph))

        for j, row in enumerate(graph):
            for i in xrange(j):
                if row[i]:
                    dsu.union(i, j)

        count = collections.Counter(dsu.find(u) for u in initial)
        ans = (-1, min(initial))
        for node in initial:
            root = dsu.find(node)
            if count[root] == 1:  # unique color
                if dsu.size(root) > ans[0]:
                    ans = dsu.size(root), node
                elif dsu.size(root) == ans[0] and node < ans[1]:
                    ans = dsu.size(root), node

        return ans[1]

复杂度分析

  • 时间复杂度： O(N^2)，其中 N 是 graph 的大小。

  • 空间复杂度： O(N)。

 Comments
On this page
0924-尽量减少恶意软件的传播