[每日一题] 928.尽量减少恶意软件的传播II

博主： Richard
发布时间：2024 年 04 月 18 日
148 次浏览
暂无评论
5916字数
分类： LeetCode

> https://leetcode.cn/problems/minimize-malware-spread-ii/description/?envType=daily-question&envId=2024-04-11

和[昨天的题](https://leetcode.cn/problems/minimize-malware-spread/?envType=daily-question&envId=2024-04-11)差不多的题目，区别是昨天的题只是清楚节点中的恶意软件，而这次是直接干掉这个节点。

### 暴力法

最简单的方法当然是暴力，直接逐个干掉 initial 里面的节点，统计干掉各个节点后网络内被感染的节点数，返回被感染数最小的节点即可。

这里用深搜或者广搜就行，我只是再写一遍并查集巩固一下 XD

```c++
int minMalwareSpread(std::vector<std::vector<int>>& graph, std::vector<int>& initial) {
    class UnionFind {
    private:
        std::vector<int> parent;
        std::vector<int> unionSize;

public:
        UnionFind() = default;

explicit UnionFind(const int &n) {
            parent.resize(n, -1);
            unionSize.resize(n, 1);
        }

void unite(const int &x, const int &y) {
            int xRoot = find(x), yRoot = find(y);
            if (xRoot == yRoot)
                return;

if (parent[xRoot] < parent[yRoot]) {
                parent[yRoot] = xRoot;
                unionSize[xRoot] += unionSize[yRoot];
            } else if (parent[xRoot] > parent[yRoot]) {
                parent[xRoot] = yRoot;
                unionSize[yRoot] += unionSize[xRoot];
            } else {
                parent[xRoot] = yRoot;
                unionSize[yRoot] += unionSize[xRoot];
                parent[yRoot] -= 1;
            }
        }

int find(const int &x) {
            return parent[x] < 0 ? x : parent[x] = find(parent[x]);
        }

void clear() {
            parent.clear();
            unionSize.clear();
        }

void resize(const int &n) {
            parent.resize(n);
            unionSize.resize(n);
            std::fill(parent.begin(), parent.end(), -1);
            std::fill(unionSize.begin(), unionSize.end(), 1);
        }

int getTreeSize(const int &x) {
            return unionSize[find(x)];
        }

int getTreeSizeByRoot(const int &x) {
            return unionSize[x];
        }
    };

int n = graph.size();
    std::unordered_map<int, int> infectedRange;
    UnionFind unionFind;

int res = n, minRange = n;
    for (const auto &exclude : initial) {
        unionFind.resize(n);
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (i != exclude && j != exclude && graph[i][j])
                    unionFind.unite(i, j);
            }
        }

infectedRange.clear();
        for (const auto &e : initial) {
            if (e == exclude)
                continue;

int curRoot = unionFind.find(e);
            infectedRange[curRoot] = unionFind.getTreeSizeByRoot(curRoot);
        }

int curRange = 0;
        for (const auto &e : infectedRange)
            curRange += e.second;

if (curRange < minRange || (curRange == minRange && exclude < res))
            res = exclude, minRange = curRange;
    }

return res;
}
```

时间复杂度 $O(m n^2 \times \alpha(n))$，空间复杂度 $O(n)$ 。其中 $m$ 为 initial 数组的长度， $n$ 为节点的个数，$\alpha(n)$ 为 Ackermman 函数的反函数。

### 并查集

拆除一个节点可能导致一个连通分量变成多个。既然如此，我们可以先把所有 initial 里的节点拆掉，这样的话图里的连通分量就只有三种情况：

1. 连通分量没有与初始感染节点连接；
2. 连通分量与一个初始感染节点连接；
3. 连通分量与多个初始感染节点连接；

显然  1, 3 两种情况是我们不需要的，只需要考虑 2 就够了。那么答案很明显，拥有最多 2 情况连通分量的节点就是我们需要的答案。

```c++
int minMalwareSpread(std::vector<std::vector<int>>& graph, std::vector<int>& initial) {
    class UnionFind {
    private:
        std::vector<int> parent;
        std::vector<int> unionSize;

public:
        UnionFind() = default;

explicit UnionFind(const int &n) {
            parent.resize(n, -1);
            unionSize.resize(n, 1);
        }

void unite(const int &x, const int &y) {
            int xRoot = find(x), yRoot = find(y);
            if (xRoot == yRoot)
                return;

int find(const int &x) {
            return parent[x] < 0 ? x : parent[x] = find(parent[x]);
        }

int getTreeSizeByRoot(const int &x) {
            return unionSize[x];
        }
    };

const int n = graph.size();

bool isPathogen[n];
    memset(isPathogen, false, sizeof(isPathogen));
    for (const auto &e : initial)
        isPathogen[e] = true;

UnionFind unionFind(n);
    for (int i = 0; i < n; ++i) {
        if (isPathogen[i])
            continue;

for (int j = i + 1; j < n; ++j) {
            if (!isPathogen[j] && graph[i][j])
                unionFind.unite(i, j);
        }
    }

std::unordered_set<int> connectedRoot[n];
    int pathogenNum[n];
    memset(pathogenNum, 0, sizeof(pathogenNum));
    for (const auto &e : initial) {
        for (int j = 0; j < n; ++j) {
            if (graph[e][j] && !isPathogen[j])
                connectedRoot[e].insert(unionFind.find(j));
        }

for (const auto &root : connectedRoot[e])
            pathogenNum[root] += 1;
    }

int res = 0, maxReduce = -1;
    for (const auto &node : initial) {
        int curReduce = 0;
        for (const auto &root : connectedRoot[node]) {
            if (pathogenNum[root] == 1)
                curReduce += unionFind.getTreeSizeByRoot(root);
        }

if (curReduce > maxReduce || (curReduce == maxReduce && node < res))
            res = node, maxReduce = curReduce;
    }

return res;
}
```

时间复杂度 $O(n^2 \times \alpha(n))$，空间复杂度 $O(n^2)$ 。其中 $n$ 为节点的个数，$\alpha(n)$ 为 Ackermman 函数的反函数。

最后修改：2024 年 04 月 21 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

[每日一题] 928.尽量减少恶意软件的传播II

Richard • 2024 年 04 月 18 日