Advertisement
Guest User

Untitled

a guest
Aug 27th, 2016
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.19 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.*;
  5. import java.util.stream.Collectors;
  6.  
  7. public class Sticks {
  8.  
  9.     public static void main(String[] args) throws IOException {
  10.         BufferedReader buffReader = new BufferedReader(new InputStreamReader(System.in));
  11.  
  12.         int sticks = Integer.parseInt(buffReader.readLine());
  13.         int stickPlacings = Integer.parseInt(buffReader.readLine());
  14.  
  15.         HashMap<Integer, Stick> allSticks = new HashMap<>();
  16.  
  17.         for (int i = 0; i < sticks; i++) {
  18.             allSticks.put(i, new Stick(i));
  19.         }
  20.  
  21.         //place sticks
  22.         for (int i = 0; i < stickPlacings; i++) {
  23.             int[] values = Arrays.stream(buffReader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
  24.             int onTop = values[0];
  25.             int below = values[1];
  26.             Stick stickOnTop = allSticks.get(onTop);
  27.             Stick stickBelow = allSticks.get(below);
  28.             allSticks.get(below).addOnTop(stickOnTop);
  29.             allSticks.get(onTop).addBelow(stickBelow);
  30.         }
  31.  
  32.         for (int i = 0; i < sticks; i++) {
  33.             Collections.sort(allSticks.get(i).below, (o1, o2) -> Integer.compare(o2.getValue(), o1.getValue()));
  34.         }
  35.         //lift
  36.         Queue<Stick> stickQueue = new LinkedList<>();
  37.  
  38.         for (int i = sticks - 1; i > 0; i--) {
  39.             Stick current = allSticks.get(i);
  40.             if (current.onTop.size() == 0) {
  41.                 stickQueue.add(current);
  42.             }
  43.         }
  44.  
  45.         HashSet<Integer> results = new LinkedHashSet<>();
  46.         boolean[] canBeLifted = new boolean[sticks];
  47.  
  48.         while (!stickQueue.isEmpty()) {
  49.             Stick current = stickQueue.poll();
  50.  
  51.             if (current.onTop.size() == 0) {
  52.                 canBeLifted[current.getValue()] = true;
  53.                 results.add(current.getValue());
  54.             }
  55.  
  56.             for (Stick stick : current.below) {
  57.                 if (!stick.onTop.contains(current)) {
  58.                     continue;
  59.                 }
  60.                 if (canBeLifted[current.getValue()]) {
  61.                     stick.onTop.remove(current);
  62.                     if (stickQueue.peek()== null || stickQueue.peek().getValue() != stick.getValue()) {
  63.                         stickQueue.add(stick);
  64.                     }
  65.                 }
  66.             }
  67.         }
  68.         if (results.size() != sticks) {
  69.             System.out.println("Cannot lift all sticks");
  70.         }
  71.         System.out.println(String.join(" ", results.stream().map(String::valueOf).collect(Collectors.toList())));
  72.     }
  73.  
  74.     private static class Stick {
  75.  
  76.         private int value;
  77.         private List<Stick> onTop;
  78.         private List<Stick> below;
  79.  
  80.         private Stick(int value) {
  81.             this.value = value;
  82.             this.onTop = new LinkedList<>();
  83.             this.below = new LinkedList<>();
  84.         }
  85.  
  86.         public void addBelow(Stick stick) {
  87.             this.below.add(stick);
  88.         }
  89.  
  90.         public void addOnTop(Stick stick) {
  91.             this.onTop.add(stick);
  92.         }
  93.  
  94.         public int getValue() {
  95.             return this.value;
  96.         }
  97.     }
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement