题目描述

在结点网络中，只有当 graph[i][j] = 1 时，每个结点 i 能够直接连接到另一个结点 j。

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

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

我们可以从初始列表中删除一个结点。如果移除这一结点将最小化 M(initial)， 则返回该结点。如果有多个结点满足条件，就返回索引最小的结点。

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

样例

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

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

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

限制

• 1 < graph.length = graph[0].length <= 300
• 0 <= graph[i][j] == graph[j][i] <= 1
• graph[i][i] = 1
• 1 <= initial.length < graph.length
• 0 <= initial[i] < graph.length

算法1

(宽度优先遍历 / BFS) $O(n^2m)$

1. 枚举删除每个初始结点 x，然后用 BFS 求出能够遍历到的结点的个数。
2. BFS 时，首先将除了 x 之外的点加入队列，然后进行遍历，统计一下最终入过队的点。

时间复杂度

• 假设共有 $n$ 个结点，$m$ 个初始结点。
• 枚举 $m$ 个初始结点，然后用 BFS 判定时间复杂度为 $O(n^2)$，故总时间复杂度为 $O(n^2m)$。

空间复杂度

• 需要 $O(n)$ 的额外空间。

C++ 代码

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size(), m = initial.size();
        int res = INT_MAX, ans = -1;

        for (int j = 0; j < m; j++) {
            queue<int> q;
            vector<bool> vis(n, false);
            int tot = 0;

            for (int i = 0; i < m; i++)
                if (initial[i] != initial[j]) {
                    q.push(initial[i]);
                    vis[initial[i]] = true;
                    tot++;
                }

            while (!q.empty()) {
                int cur = q.front();
                q.pop();
                for (int i = 0; i < n; i++)
                    if (graph[cur][i] == 1 && !vis[i]) {
                        vis[i] = true;
                        q.push(i);
                        tot++;
                    }
            }

            if (res > tot) {
                res = tot;
                ans = initial[j];
            } else if (res == tot && ans > initial[j]) {
                ans = initial[j];
            }
        }

        return ans;
    }
};

算法2

(并查集) $O(n^2 + m)$

1. 根据 graph 建立并查集，得到每个连通块的代表结点和连通块的 size。
2. 统计每个连通块有多少个初始结点。
3. 枚举删除每个初始结点，如果这个初始结点所在的连通块的初始结点个数等于 1，则说明删除这个初始结点会减少最终的感染结点的个数。找到最大的减少个数所属的初始结点。

时间复杂度

• 假设共有 $n$ 个结点，$m$ 个初始结点，并查集查找的时间复杂度为常数。
• 建立并查集的时间复杂度为 $O(n^2)$。
• 对于每个初始结点，仅需要常数的时间判定。
• 故总时间复杂度为 $O(n^2 + m)$。

空间复杂度

• 需要 $O(n)$ 的额外空间。

C++ 代码

class Solution {
private:
    vector<int> f, sz;

    int find(int x) {
        return x == f[x] ? x : f[x] = find(f[x]);
    }

public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size(), m = initial.size();

        f.resize(n);
        sz.resize(n, 1);

        for (int i = 0; i < n; i++)
            f[i] = i;

        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (graph[i][j]) {
                    int fx = find(i), fy = find(j);
                    if (fx != fy) {
                        if (sz[fx] < sz[fy]) {
                            f[fx] = fy;
                            sz[fy] += sz[fx];
                        } else {
                            f[fy] = fx;
                            sz[fx] += sz[fy];
                        }
                    }
                }

        vector<int> tot(n, 0);

        for (int i = 0; i < m; i++)
            tot[find(initial[i])]++;

        int res = -1, ans = -1;

        for (int i = 0; i < m; i++) {
            int fx = find(initial[i]);
            int cur = 0;
            if (tot[fx] == 1)
                cur = sz[fx];

            if (res < cur) {
                res = cur;
                ans = initial[i];
            } else if (res == cur && ans > initial[i]) {
                ans = initial[i];
            }
        }

        return ans;
    }
};