fork(1) download
copy 
  1. import java.util.*;
  2.  
  3.  
  4. public class Main {
  5.      class Vertex {
  6.         int index;
  7.         boolean hidden;
  8.         List<Vertex> childs = new ArrayList<>();
  9.  
  10.         public Vertex(int index) {
  11.             this.index = index;
  12.         }
  13.     }
  14.  
  15.     public static void main(String[] args) {
  16.         new Main().run();
  17.     }
  18.  
  19.     void run() {
  20.         int n = 10;
  21.         ArrayList<Vertex> tree = new ArrayList<>();
  22.         HashMap<Integer, List<Integer>> childListMap = new HashMap<>();
  23.         childListMap.put(0, Arrays.asList(1, 2, 3));
  24.         childListMap.put(2, Arrays.asList(4));
  25.         childListMap.put(3, Arrays.asList(7));
  26.         childListMap.put(4, Arrays.asList(5, 6));
  27.         childListMap.put(7, Arrays.asList(8, 9));
  28.  
  29.         HashSet<Integer> hiddenSet = new HashSet<>();
  30.         hiddenSet.addAll(Arrays.asList(5, 6));
  31.  
  32.         Vertex[] vs = new Vertex[n];
  33.         for (int i = 0; i < n; i++) {
  34.             Vertex v = new Vertex(i);
  35.             v.hidden = hiddenSet.contains(i);
  36.             vs[i] = v;
  37.         }
  38.         for (int i = 0; i < n; i++) {
  39.             if (childListMap.get(i) == null)
  40.                 continue;
  41.             for (Integer childIndex : childListMap.get(i)) {
  42.                 vs[i].childs.add(vs[childIndex]);
  43.             }
  44.         }
  45.         setHiddenForTree(vs[0]);
  46.         printResult(vs);
  47.     }
  48.  
  49.     void setHiddenForTree(Vertex root) {
  50.         dfs(root);
  51.     }
  52.  
  53.     boolean dfs(Vertex v) {
  54.         if (v.hidden) {
  55.             return true;
  56.         }
  57.         if (v.childs.isEmpty()){
  58.             return v.hidden;
  59.         }
  60.         boolean allChildsHidden = true;
  61.         for (Vertex child : v.childs) {
  62.             allChildsHidden = allChildsHidden & dfs(child); //if at least one child isn't hidden, result of boolean product will be 'false'
  63.         }
  64.         if (allChildsHidden) {
  65.             v.hidden = true;
  66.         }
  67.         return v.hidden;
  68.     }
  69.  
  70.     void printResult(Vertex[] vs) {
  71.         for (int i = 0; i < vs.length; i++) {
  72.             System.out.println("vertex " + i + ": " + "hidden = " + vs[i].hidden);
  73.         }
  74.     }
  75. }
  76.  
Success #stdin #stdout 0.04s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
vertex 0: hidden = false
vertex 1: hidden = false
vertex 2: hidden = true
vertex 3: hidden = false
vertex 4: hidden = true
vertex 5: hidden = true
vertex 6: hidden = true
vertex 7: hidden = false
vertex 8: hidden = false
vertex 9: hidden = false
https://ideone.com/N3qJRV
language:
Java (HotSpot 12)
created:
8 years 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!