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

/*
 * 思路：
 * 1. 使用DFS（深度优先搜索）来找到每个节点可以感染的所有节点。
 * 2. 计算每个初始感染节点的贡献值，即移除该节点后，减少的感染节点数。
 * 3. 返回贡献值最大的节点，如果有多个，返回索引最小的节点。
 */

import java.util.*;
import java.util.stream.*;

public class Solution {
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;
        int[] infectedBy = new int[n];
        Arrays.fill(infectedBy, -1);

        for (int node : initial) {
            dfs(graph, node, node, infectedBy, new boolean[n]);
        }

        int[] contribution = new int[n];
        IntStream.range(0, n).filter(i -> infectedBy[i] != -1).forEach(i -> contribution[infectedBy[i]]++);

        return Arrays.stream(initial)
                     .boxed()
                     .min((a, b) -> contribution[a] != contribution[b] ? Integer.compare(contribution[b], contribution[a]) : Integer.compare(a, b))
                     .orElse(-1);
    }

    private void dfs(int[][] graph, int start, int infected, int[] infectedBy, boolean[] visited) {
        if (visited[start]) return;
        visited[start] = true;
        infectedBy[start] = infected;
        for (int i = 0; i < graph.length; i++) {
            if (graph[start][i] == 1 && !visited[i]) {
                dfs(graph, i, infected, infectedBy, visited);
            }
        }
    }
}