// Complete the repair_machine function below.
void dfs(int cur, const int &n, const vector
vector
int &cc_initials) {
vis[cur] = true;
cc_size += 1;
cc_initials += is_initial[cur];
for (int nxt = 0; nxt < n; ++nxt)
if (graph[cur][nxt] && !vis[nxt])
dfs(nxt, n, graph, vis, is_initial, cc_size, cc_initials);
}
vector
int n = network.size();
vector
for (int i = 0; i < initial_machines.size(); ++i)
is_initial[initial_machines[i]] = true;
int ans = n, ans_cnt = 0;
vector
for (int i = 0; i < initial_machines.size(); ++i) {
int cur = initial_machines[i];
int contribution = 0;
if (!vis[cur]) {
int cc_size = 0, cc_initials = 0;
dfs(cur, n, network, vis, is_initial, cc_size, cc_initials);
if (cc_initials == 1)
contribution = cc_size;
}
if (contribution > ans_cnt || (contribution == ans_cnt && cur < ans)) {
ans = cur;
ans_cnt = contribution;
}
}
res.push_back(ans);
res.push_back(ans_cnt);
return res;
}
a data center is represented by a matrix, if matrix[j] = 1 then machine i and machine j are connected, if matrix[j] = 0, they are not connected. Right now, if a malware infected one machine, then it can spread to all the interconnected machines until there are no more reacheable machines to infect.
You also know which machines are intial infected, but you only have enough time to fix a single one. Your goal is to choose the machine that will result in the maximum effect - defined as the largest difference in the final state of the data center if a single inital machine is repaired.
example:
[1 0 0]
[0 1 0]
[0 0 1]
two infected machines [0, 1]
result: [0, 1]
method: List