题目描述

(这道题目类似于LeetCode 924. Minimize Malware Spread，不同之处用已加粗)。

在一个网络中，节点i和节点j相邻，当且仅当graph[i][j] = 1。

一些节点，存于initial中，已经被恶意软件感染。如果两个相邻的节点中，其中一个节点被感染，则另一个节点也会被感染。这种感染方式会持续进行，直到没有新节点被感染为止。

假设M(initial)表示整个网络最终被感染的节点数。

我们可以从整个网络中 完全删掉一个节点，及其关联的所有边 。
请返回删除后，可使M(initial)最小的点。如果答案不唯一，请返回编号最小的点。

注意：

1. 1 < graph.length = graph[0].length <= 300
2. 0 <= graph[i][j] == graph[j][i] <= 1
3. graph[i][i] = 1
4. 1 <= initial.length < graph.length
5. 0 <= initial[i] < graph.length

样例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

算法

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

首先我们先将所有的病毒节点去掉，然后将所有连通块合并成一个节点。
这是因为一个连通块中的节点，要么全部被感染，要么全部不被感染，所以我们可以将它们当成一个整体来考虑。

然后我们统计一下所有连通块，直接相邻的病毒节点的个数。
对于一个连通块：

• 如果直接相邻的病毒节点的个数为0，则一定不会被感染，忽略之；
• 如果直接相邻的病毒节点的个数为1，则将该病毒节点删除后，整个连通块就可以避免被感染；
• 如果直接相邻的病毒节点的个数大于等于2，则不管删除哪个病毒节点，该连通块都仍会被感染，忽略之；

所以我们只需在所有第二种连通块（直接相邻的病毒节点的个数为1的连通块）中，找出节点个数最多的连通块，与它相邻的病毒节点就是我们要删除的节点；如果有多个连通块节点个数相同，我们找出与之对应的编号最小的病毒节点即可。

时间复杂度分析：

• 合并所有非病毒节点的连通块：$O(n^2)$；
• 统计每个连通块节点的个数：$O(n)$；
• 统计每个连通块连接的病毒节点个数：$O(n^2)$；
• 遍历所有连通块，求需要删除的节点：$O(n)$；

所以总时间复杂度是 $O(n^2)$。

C++ 代码

class Solution {
public:

    vector<int> p;

    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        unordered_set<int> S;
        for (auto v : initial) S.insert(v);
        int n = graph.size();
        for (int i = 0; i < n; i ++ ) p.push_back(i); // 初始化并查集

        for (int i = 0; i < n; i ++ ) // 合并所有没有被病毒感染的点
            for (int j = 0; j < n; j ++ )
                if (S.count(i) == 0 && S.count(j) == 0 && graph[i][j])
                {
                    p[find(i)] = find(j);
                }

        unordered_map<int, int> comp_cnt; // 统计每个连通块的节点个数
        for (int i = 0; i < n; i ++ )
            if (S.count(i) == 0)
                comp_cnt[find(i)] ++ ;

        unordered_map<int, unordered_set<int>> comp_infect; // 统计每个连通块连接的病毒节点个数
        for (auto i : initial)
            for (int j = 0; j < n; j ++ )
                if (S.count(j) == 0 && graph[i][j])
                    comp_infect[find(j)].insert(i);

        int m = -1, res = initial[0];
        for (auto v : initial) res = min(res, v);
        for (auto item : comp_infect)
        {
            if (item.second.size() == 1)
            {
                int ver = *item.second.begin();
                int cnt = comp_cnt[item.first];
                if (cnt > m)
                {
                    m = cnt;
                    res = ver;
                }
                else if (cnt == m && res > ver)
                    res = ver;
            }
        }

        return res;
    }
};