fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_set>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. class Solution {
  8. public:
  9.     int g_nodes, g_edges;
  10.     vector<vector<int>> adj;
  11.  
  12.     // DFS to calculate the number of infected nodes
  13.     int dfs(int node, vector<bool>& visited, vector<int>& malware) {
  14.         visited[node] = true;
  15.         int infectedCount = 1; // Start counting the current infected node
  16.  
  17.         for (int neighbor : adj[node]) {
  18.             if (!visited[neighbor] && malware[neighbor] == 1) {
  19.                 infectedCount += dfs(neighbor, visited, malware);
  20.             }
  21.         }
  22.         return infectedCount;
  23.     }
  24.  
  25.     // Main function to remove one node and minimize the malware spread
  26.     int minMalwareSpread(vector<int>& g_from, vector<int>& g_to, vector<int>& malware) {
  27.         adj.resize(g_nodes);
  28.  
  29.         // Build the graph
  30.         for (int i = 0; i < g_edges; ++i) {
  31.             adj[g_from[i] - 1].push_back(g_to[i] - 1);
  32.             adj[g_to[i] - 1].push_back(g_from[i] - 1);
  33.         }
  34.  
  35.         int minInfected = g_nodes + 1; // Initialize with a large number
  36.         int result = -1;
  37.  
  38.         // Try removing each infected node
  39.         for (int i = 0; i < g_nodes; ++i) {
  40.             if (malware[i] == 1) {
  41.                 // Create a copy of the malware array and remove the current node
  42.                 vector<int> malwareCopy = malware;
  43.                 malwareCopy[i] = 0;
  44.  
  45.                 // Perform DFS to calculate the spread of malware
  46.                 vector<bool> visited(g_nodes, false);
  47.                 int infectedCount = 0;
  48.  
  49.                 for (int j = 0; j < g_nodes; ++j) {
  50.                     if (!visited[j] && malwareCopy[j] == 1) {
  51.                         infectedCount += dfs(j, visited, malwareCopy);
  52.                     }
  53.                 }
  54.  
  55.                 // Update the result if this removal minimizes the infected count
  56.                 if (infectedCount < minInfected) {
  57.                     minInfected = infectedCount;
  58.                     result = i;
  59.                 } else if (infectedCount == minInfected && i < result) {
  60.                     result = i;
  61.                 }
  62.             }
  63.         }
  64.  
  65.         return result;
  66.     }
  67. };
  68.  
  69. int main() {
  70.     int g_nodes = 5;
  71.     int g_edges = 4;
  72.     vector<int> g_from = {1, 2, 3, 4};
  73.     vector<int> g_to = {2,3,4,5};
  74.     vector<int> malware = {0,0,0,0,0};
  75.  
  76.     Solution sol;
  77.     sol.g_nodes = g_nodes;
  78.     sol.g_edges = g_edges;
  79.     int nodeToRemove = sol.minMalwareSpread(g_from, g_to, malware);
  80.  
  81.     cout << "Remove node: " << nodeToRemove + 1 << endl; // Convert 0-indexed to 1-indexed
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Remove node: 0
https://ideone.com/8HV4TO
language:
C++ (gcc 8.3)
created:
119 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!