fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.  
  11. 	public static void main (String[] args) throws java.lang.Exception
  12. 	{
  13. 		// your code goes here
  14. 	}
  15.  
  16.     public int minimizeInfectionBruteForce(int n, int[] from, int[] to, int[] infected) {
  17.  
  18.         int finalAnswer = Integer.MAX_VALUE;
  19.         int minInfectedAfterSpread = Integer.MAX_VALUE;
  20.  
  21.         // Try removing each node
  22.         for (int remove = 0; remove < n; remove++) {
  23.  
  24.             // Step 1: Build new graph without 'remove'
  25.             List<Integer>[] graph = new ArrayList[n];
  26.             for (int i = 0; i < n; i++) {
  27.                 graph[i] = new ArrayList<>();
  28.             }
  29.  
  30.             for (int i = 0; i < from.length; i++) {
  31.                 int u = from[i];
  32.                 int v = to[i];
  33.  
  34.                 if (u == remove || v == remove) continue;
  35.  
  36.                 graph[u].add(v);
  37.                 graph[v].add(u);
  38.             }
  39.  
  40.             boolean[] visited = new boolean[n];
  41.             int infectedAfterSpread = 0;
  42.  
  43.             // Step 2: DFS each component
  44.             for (int i = 0; i < n; i++) {
  45.  
  46.                 if (i == remove) continue;
  47.  
  48.                 if (!visited[i]) {
  49.  
  50.                     int[] result = dfs(i, remove, graph, visited, infected);
  51.  
  52.                     int componentSize = result[0];
  53.                     int infectedCount = result[1];
  54.  
  55.                     if (infectedCount > 0) {
  56.                         infectedAfterSpread += componentSize;
  57.                     }
  58.                 }
  59.             }
  60.  
  61.             // Step 3: Track best removal
  62.             if (infectedAfterSpread < minInfectedAfterSpread) {
  63.                 minInfectedAfterSpread = infectedAfterSpread;
  64.                 finalAnswer = remove;
  65.             } else if (infectedAfterSpread == minInfectedAfterSpread) {
  66.                 finalAnswer = Math.min(finalAnswer, remove);
  67.             }
  68.         }
  69.  
  70.         return finalAnswer;
  71.     }
  72.  
  73.     private int[] dfs(int node, int remove,
  74.                       List<Integer>[] graph,
  75.                       boolean[] visited,
  76.                       int[] infected) {
  77.  
  78.         Stack<Integer> stack = new Stack<>();
  79.         stack.push(node);
  80.  
  81.         int componentSize = 0;
  82.         int infectedCount = 0;
  83.  
  84.         while (!stack.isEmpty()) {
  85.  
  86.             int curr = stack.pop();
  87.  
  88.             if (visited[curr]) continue;
  89.             visited[curr] = true;
  90.  
  91.             componentSize++;
  92.  
  93.             if (infected[curr] == 1) {
  94.                 infectedCount++;
  95.             }
  96.  
  97.             for (int neighbor : graph[curr]) {
  98.                 if (!visited[neighbor] && neighbor != remove) {
  99.                     stack.push(neighbor);
  100.                 }
  101.             }
  102.         }
  103.  
  104.         return new int[]{componentSize, infectedCount};
  105.     }
  106.  
  107. }
Success #stdin #stdout 0.12s 54564KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eas82l
language:
Java (HotSpot 12)
created:
5 hours 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!