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.  
  40.         for (int x = 1; x <= n; x++) {
  41.  
  42.             graph = new ArrayList<>();
  43.             for (int i = 0; i <= n; i++) {
  44.                 graph.add(new ArrayList<>());
  45.             }
  46.  
  47.             for (int i = 0; i < m; i++) {
  48.                 int u = edges[i][0];
  49.                 int v = edges[i][1];
  50.  
  51.                 if (u == x || v == x) continue;
  52.  
  53.                 graph.get(u).add(v);
  54.                 graph.get(v).add(u);
  55.             }
  56.  
  57.             visited = new boolean[n + 1];
  58.             int answer = 0;
  59.  
  60.  
  61.             for (int i = 1; i <= n; i++) {
  62.  
  63.                 if (i == x) continue;
  64.  
  65.                 if (!visited[i]) {
  66.                     greenCount = 0;
  67.                     componentSize = 0;
  68.  
  69.                     dfs(i);
  70.  
  71.                     if (greenCount >= 1) {
  72.                         answer += componentSize;
  73.                     }
  74.                 }
  75.             }
  76.  
  77.             finalAnswer = Math.min(finalAnswer, answer);
  78.         }
  79.  
  80.         return finalAnswer;
  81.     }
  82.  
  83.  
  84.     public static void main(String[] args) {
  85.  
  86.         int n = 5;
  87.  
  88.         int[][] edges = {
  89.             {1, 2},
  90.             {2, 3},
  91.             {3, 4},
  92.             {4, 5}
  93.         };
  94.  
  95.  
  96.         boolean[] greenNodes = new boolean[n + 1];
  97.         greenNodes[2] = true;
  98.         greenNodes[5] = true;
  99.  
  100.         int result = solve(n, edges, greenNodes);
  101.         System.out.println(result);
  102.     }
  103. }
Success #stdin #stdout 0.12s 54640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/r8NVrm
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!