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

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

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

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

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

我们可以从 initial 中 删除一个节点 ， 并完全移除该节点以及从该节点到任何其他节点的任何连接。

请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引 最小的节点 。

示例 1：

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

示例 2：

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

示例 3：

**输入：** graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
**输出：** 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 中每个整数都 不同

方法一： 深度优先搜索

思路和算法

首先构建一个图 G，其节点为所有不在 initial 中的剩余节点。

对于不在 initial 中的节点 v，检查会被 initial 中哪些节点 u 感染。 之后再看哪些节点 v 只会被一个节点 u 感染。具体的算法可以看代码中的注释。

[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
class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int N = graph.length;
        int[] clean = new int[N];
        Arrays.fill(clean, 1);
        for (int x: initial)
            clean[x] = 0;

        // For each node u in initial, dfs to find
        // 'seen': all nodes not in initial that it can reach.
        ArrayList<Integer>[] infectedBy = new ArrayList[N];
        for (int i = 0; i < N; ++i)
            infectedBy[i] = new ArrayList();

        for (int u: initial) {
            Set<Integer> seen = new HashSet();
            dfs(graph, clean, u, seen);
            for (int v: seen)
                infectedBy[v].add(u);
        }

        // For each node u in initial, for every v not in initial
        // that is uniquely infected by u, add 1 to the contribution for u.
        int[] contribution = new int[N];
        for (int v = 0; v < N; ++v)
            if (infectedBy[v].size() == 1)
                contribution[infectedBy[v].get(0)]++;

        // Take the best answer.
        Arrays.sort(initial);
        int ans = initial[0], ansSize = -1;
        for (int u: initial) {
            int score = contribution[u];
            if (score > ansSize || score == ansSize && u < ans) {
                ans = u;
                ansSize = score;
            }
        }
        return ans;
    }

    public void dfs(int[][] graph, int[] clean, int u, Set<Integer> seen) {
        for (int v = 0; v < graph.length; ++v)
            if (graph[u][v] == 1 && clean[v] == 1 && !seen.contains(v)) {
                seen.add(v);
                dfs(graph, clean, v, seen);
            }
    }
}
[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
class Solution(object):
    def minMalwareSpread(self, graph, initial):
        N = len(graph)
        clean = set(range(N)) - set(initial)
        def dfs(u, seen):
            for v, adj in enumerate(graph[u]):
                if adj and v in clean and v not in seen:
                    seen.add(v)
                    dfs(v, seen)

        # For each node u in initial, dfs to find
        # 'seen': all nodes not in initial that it can reach.
        infected_by = {v: [] for v in clean}
        for u in initial:
            seen = set()
            dfs(u, seen)

            # For each node v that was seen, u infects v.
            for v in seen:
                infected_by[v].append(u)

        # For each node u in initial, for every v not in initial
        # that is uniquely infected by u, add 1 to the contribution for u.
        contribution = collections.Counter()
        for v, neighbors in infected_by.iteritems():
            if len(neighbors) == 1:
                contribution[neighbors[0]] += 1

        # Take the best answer.
        best = (-1, min(initial))
        for u, score in contribution.iteritems():
            if score > best[0] or score == best[0] and u < best[1]:
                best = score, u
        return best[1]

复杂度分析

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

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

方法二： 并查集

思路

对于并查集中的一个集合，集合中会有一定数量的节点在 initial 里面，只需要关注那些只有一个 initial 节点的集合就可以了。

算法

首先构建一个图 G，其节点为所有不在 initial 中的剩余节点。然后用并查集找出所有的连通分量。

对于原始图中的每条边 n => v，u 为 initial 中的节点，v 为不在 initial 中的节点。对于 initial 中的每个节点 u，如果 u 所在的集合中只有它是唯一的 initial 节点，那么这个集合的大小就是移除 u 之后能得到的收益。

之后遍历所有的可能找到最终答案。

[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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int N = graph.length;
        DSU dsu = new DSU(N);

        // clean[u] == 1 if its a node in the graph not in initial.
        int[] clean = new int[N];
        Arrays.fill(clean, 1);
        for (int x: initial) clean[x] = 0;

        for (int u = 0; u < N; ++u) if (clean[u] == 1)
            for (int v = 0; v < N; ++v) if (clean[v] == 1)
                if (graph[u][v] == 1)
                    dsu.union(u, v);

        // dsu now represents the components of the graph without
        // any nodes from initial.  Let's call this graph G.
        int[] count = new int[N];
        Map<Integer, Set<Integer>> nodeToCompo = new HashMap();
        for (int u: initial) {
            Set<Integer> components = new HashSet();
            for (int v = 0; v < N; ++v) if (clean[v] == 1) {
                if (graph[u][v] == 1)
                    components.add(dsu.find(v));
            }

            nodeToCompo.put(u, components);
            for (int c: components)
                count[c]++;
        }

        // For each node u in initial, nodeToCompo.get(u)
        // now has every component from G that u neighbors.

        int ans = -1, ansSize = -1;
        for (int u: nodeToCompo.keySet()) {
            Set<Integer> components = nodeToCompo.get(u);
            int score = 0;
            for (int c: components)
                if (count[c] == 1) // uniquely infected
                    score += dsu.size(c);

            if (score > ansSize || score == ansSize && u < ans) {
                ansSize = score;
                ans = u;
            }
        }

        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)];
    }
}
[solutiion2-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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
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):
        N = len(graph)
        initial_set = set(initial)
        clean = [x for x in range(N) if x not in initial_set]

        # clean[u] == 1 if its a node in the graph not in initial.
        dsu = DSU(N)
        for u in clean:
            for v in clean:
                if graph[u][v]:
                    dsu.union(u, v)

        # dsu now represents the components of the graph without
        # any nodes from initial.  Let's call this graph G.
        count = collections.Counter()
        node_to_compo = {}
        for u in initial:
            components = set()
            for v in clean:
                if graph[u][v]:
                    components.add(dsu.find(v))
            node_to_compo[u] = components

            for c in components:
                count[c] += 1

        # For each node u in initial, nodeToCompo.get(u)
        # now has every component from G that u neighbors.

        best = (-1, None) # score, node
        for u, components in node_to_compo.iteritems():
            score = 0
            for c in components:
                if count[c] == 1: #uniquely infected
                    score += dsu.size(c)
            if score > best[0] or score == best[0] and u < best[1]:
                best = (score, u)

        return best[1]

复杂度分析

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

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

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