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. 	static List<List<Integer>> graph;
  11.     static boolean[] visited;
  12.     static boolean[] isGreen;
  13.  
  14.     static int greenCount;
  15.     static int componentSize;
  16.  
  17.  
  18.     static void dfs(int node) {
  19.         visited[node] = true;
  20.         componentSize++;
  21.  
  22.         if (isGreen[node]) {
  23.             greenCount++;
  24.         }
  25.  
  26.         for (int neighbour : graph.get(node)) {
  27.             if (!visited[neighbour]) {
  28.                 dfs(neighbour);
  29.             }
  30.         }
  31.     }
  32.  
  33.     public static int solve(int n, int[][] edges, boolean[] greenNodes) {
  34.  
  35.         int m = edges.length;
  36.         isGreen = greenNodes;
  37.         int finalAnswer = Integer.MAX_VALUE;
  38.  
  39.         // Try deleting each node
  40.         for (int x = 1; x <= n; x++) {
  41.  
  42.             // Build new graph excluding node x
  43.             graph = new ArrayList<>();
  44.             for (int i = 0; i <= n; i++) {
  45.                 graph.add(new ArrayList<>());
  46.             }
  47.  
  48.             for (int i = 0; i < m; i++) {
  49.                 int u = edges[i][0];
  50.                 int v = edges[i][1];
  51.  
  52.                 if (u == x || v == x) continue;
  53.  
  54.                 graph.get(u).add(v);
  55.                 graph.get(v).add(u);
  56.             }
  57.  
  58.             visited = new boolean[n + 1];
  59.             int answer = 0;
  60.  
  61.  
  62.             for (int i = 1; i <= n; i++) {
  63.  
  64.                 if (i == x) continue;
  65.  
  66.                 if (!visited[i]) {
  67.                     greenCount = 0;
  68.                     componentSize = 0;
  69.  
  70.                     dfs(i);
  71.  
  72.                     if (greenCount >= 1) {
  73.                         answer += componentSize;
  74.                     }
  75.                 }
  76.             }
  77.  
  78.             finalAnswer = Math.min(finalAnswer, answer);
  79.         }
  80.  
  81.         return finalAnswer;
  82.     }
  83.  
  84.  
  85.     public static void main(String[] args) {
  86.  
  87.         int n = 5;
  88.  
  89.         int[][] edges = {
  90.             {1, 2},
  91.             {2, 3},
  92.             {3, 4},
  93.             {4, 5}
  94.         };
  95.  
  96.  
  97.         boolean[] greenNodes = new boolean[n + 1];
  98.         greenNodes[2] = true;
  99.         greenNodes[5] = true;
  100.  
  101.         int result = solve(n, edges, greenNodes);
  102.         System.out.println(result);
  103.     }
  104. }
Success #stdin #stdout 0.08s 54344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/QNXoku
language:
Java (HotSpot 12)
created:
2 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!