年终奖人均64万元，创公司成立以来最高纪录。|最高纪录|算法

1月19日全球内存巨头SK海力士将向全体员工发放人均超1.36亿韩元(约合64万元人民币)的绩效奖金，创公司成立以来最高纪录。员工能拿到这笔巨额奖金的重要原因在于，去年9月，海力士与工会达成历史性劳资协议，废除此前“利润分享不超过基本工资10倍”的上限，改为年度营业利润的10%。

SK海力士2025年年度营业利润估计为43.8312万亿韩元，按10%计提绩效奖金约4.38万亿韩元（折合207亿元人民币）。它之所以这么豪横，底气主要来自于最近几年人工智能的快速崛起。SK海力是士主要生产和设计存储数据的芯片。比如我们电脑上的内存条，SSD固态硬盘等。这里也祝愿大家今年年终奖也都能拿这么多。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第924题：尽量减少恶意软件的传播，难度是困难。

给出了一个由 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,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 中所有整数均不重复

问题分析

这题描述的比较绕，我用大白话来描述一下就比较简单了。说的是给定一个无向图graph，图不一定是连通的，然后再给一个数组initial，它是图中的某些顶点，表示的是最初的病毒。只要是和病毒相连的顶点都会被病毒个感染，题中说的是从图中移除一个顶点，让被感染的顶点个数最少。

在一个连通图中只要有一个病毒，那么这个连通图中所有顶点就都会被感染。一个连通图也就是一个连通分量。因为题中说了只能移除一个顶点，如果在一个连通分量中只有一个病毒，我们把它移除，那么这个连通分量中的其他顶点就都不会被感染了，如果有多个连通分量在最初的时候都只有一个顶点被感染，我们移除连通分量节点个数最多的那个即可。

如果一个连通分量在最初的时候没有任何病毒，则不需要移除。如果一个连通分量有两个及以上的病毒，无论移除哪个，其他顶点也都会被感染。所以我们这里只移除连通分量在最初的时候只有一个病毒的那个顶点。

如果没有任何连通分量在最初的时候只有一个病毒，就移除initiate中最小的值即可（这是题中的要求，如果有多个节点满足条件，就返回索引最小的节点）。

JAVA：

private int curCnt; // 记录当前连通分量的节点个数
privateint initialCnt;// 记录当前连通分量中最初被感染的数量
privateint minVertexId;// 当前连通分量中最初被感染的最小编号

 public int minMalwareSpread(int[][] graph, int[] initial) {
    int n = graph.length;
    boolean[] vis = newboolean[n];// 标记顶点是否被访问过
    boolean[] isInitial = newboolean[n];// 标记初始感染的节点
    int mInit = n;// 记录初始被感染的最小节点编号
    for (int x : initial) {
        isInitial[x] = true;
        mInit = Math.min(mInit, x);
    }

     int ans = -1;// 最终要移除的节点
    int maxSize = 0;// 要移除节点所在的连通分量的顶点个数
    for (int x : initial) {// 遍历最初的恶意软件节点
        if (vis[x])// 该顶点已经被访问过，则跳过
            continue;
        // 遍历当前连通分量的时候，下面3个变量都要重新初始化。
        curCnt = 0;
        initialCnt = 0;
        minVertexId = n;
        dfs(x, graph, vis, isInitial);// 只要x能访问到的节点都能被感染。
        // 当前连通分量中最初被感染的恶意软件数量只有是 1 ，我们把它移除，M才会最小。
        if (initialCnt == 1 && (curCnt > maxSize || curCnt == maxSize && minVertexId < ans)) {
            ans = minVertexId;
            maxSize = curCnt;
        }
    }
    // 如果不能移除，则返回最初被感染的最小编号
    return ans < 0 ? mInit : ans;
}

 private void dfs(int x, int[][] graph, boolean[] vis, boolean[] isInitial) {
    vis[x] = true;
    curCnt++;// 统计当前连通分量的顶点个数
    if (isInitial[x]) {
        initialCnt++;// 该连通分量中恶意软件的数量
        minVertexId = Math.min(minVertexId, x);
    }
    for (int i = 0; i < graph[x].length; i++) {
        if (graph[x][i] == 1 && !vis[i])
            dfs(i, graph, vis, isInitial);
    }
}

C++：

private:
    // 对应Java中的私有成员变量
    int curCnt;          // 记录当前连通分量的节点个数
    int initialCnt;      // 记录当前连通分量中最初被感染的数量
    int minVertexId;     // 当前连通分量中最初被感染的最小编号

     // 深度优先搜索，遍历连通分量并统计关键信息
    void dfs(int x, vector> &graph, vector &vis, vector &isInitial) {
        vis[x] = true;
        curCnt++; // 统计当前连通分量的节点数

         // 如果当前节点是初始感染节点，更新统计信息
        if (isInitial[x]) {
            initialCnt++;
            minVertexId = min(minVertexId, x);
        }

         // 遍历当前节点的所有邻接节点
        for (int i = 0; i < graph[x].size(); i++) {
            // 邻接且未访问过的节点，递归遍历
            if (graph[x][i] == 1 && !vis[i]) {
                dfs(i, graph, vis, isInitial);
            }
        }
    }

 public:
    int minMalwareSpread(vector> &graph, vector &initial) {
        int n = graph.size();
        vector vis(n, false);       // 标记节点是否被访问过
        vector isInitial(n, false); // 标记节点是否是初始感染节点
        int mInit = n;                    // 初始感染节点的最小编号

         // 初始化isInitial数组，并找到初始感染节点的最小编号
        for (int x: initial) {
            isInitial[x] = true;
            mInit = min(mInit, x);
        }

         int ans = -1;      // 最终要移除的节点
        int maxSize = 0;   // 移除节点后能减少的最大感染节点数

         // 遍历每个初始感染节点，分析其所在连通分量
        for (int x: initial) {
            if (vis[x]) { // 已访问过的连通分量跳过
                continue;
            }

             // 重置当前连通分量的统计变量
            curCnt = 0;
            initialCnt = 0;
            minVertexId = n;

             // 遍历当前节点所在的连通分量
            dfs(x, graph, vis, isInitial);

             // 仅当连通分量中只有1个初始感染节点时，移除该节点才有意义
            if (initialCnt == 1) {
                // 优先选连通分量更大的，若大小相同则选编号更小的
                if (curCnt > maxSize || (curCnt == maxSize && minVertexId < ans)) {
                    ans = minVertexId;
                    maxSize = curCnt;
                }
            }
        }

         // 若无有效移除节点，返回初始感染的最小编号；否则返回最优节点
        return ans < 0 ? mInit : ans;
    }