https://leetcode.cn/problems/minimize-malware-spread-ii/description/?envType=daily-question&envId=2024-04-11
和昨天的题差不多的题目,区别是昨天的题只是清楚节点中的恶意软件,而这次是直接干掉这个节点。
暴力法
最简单的方法当然是暴力,直接逐个干掉 initial 里面的节点,统计干掉各个节点后网络内被感染的节点数,返回被感染数最小的节点即可。
这里用深搜或者广搜就行,我只是再写一遍并查集巩固一下 XD
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, 3 两种情况是我们不需要的,只需要考虑 2 就够了。那么答案很明显,拥有最多 2 情况连通分量的节点就是我们需要的答案。
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]);
}
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 函数的反函数。