题目描述

(这个问题与 Minimize Malware Spread 是一样的，不同之处用粗体表示。)

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

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

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

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

样例

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

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

输入：graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
输出：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 之外的点加入队列，然后进行遍历，统计一下最终入过队的点。
3. 注意，这道题在遍历时不能将与 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 ans = INT_MAX, id = -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 (i != initial[j] && graph[cur][i] == 1 && !vis[i]) {
                        vis[i] = true;
                        q.push(i);
                        tot++;
                    }
            }

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

算法2

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

1. 去掉 initial 结点，根据剩余结点的图建立并查集，得到每个连通块的代表结点和连通块的 size。
2. 统计每个连通块与多少个初始结点直接相连。
3. 枚举删除每个初始结点，如果某个连通块与这个初始结点直接相连，且直接相连的个数为 1，则说明删除这个初始结点将导致这个初始结点不再被感染。

时间复杂度

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

        vector<bool> init(n, false);
        for (int i = 0; i < m; i++)
            init[initial[i]] = true;

        for (int i = 0; i < n; i++)
            if (!init[i])
                for (int j = i + 1; j < n; j++)
                    if (!init[j] && 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++) {
            vector<bool> seen(n, false);
            for (int j = 0; j < n; j++)
                if (!init[j] && graph[initial[i]][j]) {
                    int fx = find(j);
                    if (!seen[fx]) {
                        tot[fx]++;
                        seen[fx] = true;
                    }
                }
        }

        int res = -1, ans = -1;
        for (int i = 0; i < m; i++) {
            vector<bool> seen(n, false);
            int cur = 0;
            for (int j = 0; j < n; j++)
                if (!init[j] && graph[initial[i]][j]) {
                    int fx = find(j);
                    if (!seen[fx]) {
                        seen[fx] = true;

                        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;
    }
};