逆向处理|并查集

Solve and verify once it occurs

lc924

逆向思维 抽象为 连通块问题

在恶意软件传播的网络中，从初始感染节点里删一个节点，找出能让最终感染节点数最少的节点，若有多个则返回索引最小的

DFS遍历未感染节点连通域

统计仅受单个初始感染节点影响的区域大小，找到删除后能最大程度减少感染的初始节点，无则返回初始节点中的最小值

924题

并查集/DFS统计感染源支配的连通域，选删除后减少感染最多的节点

928题

DFS标记单感染源连通域，计算删除节点后可保护的节点数，选最优节点（多解选索引最小）

class Solution {
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial)

{
unordered_set<int> st(initial.begin(), initial.end());
vector<int> vis(graph.size());
int node_id, size;
function<void(int)> dfs = [&](int x) {
vis[x] = true;
size++;
for (int y = 0; y < graph[x].size(); y++) {
if (graph[x][y] == 0) {
continue;
}
if (st.contains(y)) {
// 按照 924 题的状态机更新 node_id
// 注意避免重复统计，例如上图中的 0 有两条不同路径可以遇到 1
if (node_id != -2 && node_id != y) {
node_id = node_id == -1 ? y : -2;
}
} else if (!vis[y]) {
dfs(y);
}
}
};

unordered_map<int, int> cnt;
for (int i = 0; i < graph.size(); i++) {
if (vis[i] || st.contains(i)) {
continue;
}
node_id = -1;
size = 0;
dfs(i);
if (node_id >= 0) { // 只找到一个在 initial 中的节点
// 删除节点 node_id 可以让 size 个点不被感染
cnt[node_id] += size;
}
}

int max_cnt = 0;
int min_node_id = 0;
for (auto [node_id, c] : cnt) {
if (c > max_cnt || c == max_cnt && node_id < min_node_id) {
max_cnt = c;
min_node_id = node_id;
}
}
return cnt.empty() ? ranges::min(initial) : min_node_id;
}
};