Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.*;
- import java.util.stream.Collectors;
- public class Sticks {
- public static void main(String[] args) throws IOException {
- BufferedReader buffReader = new BufferedReader(new InputStreamReader(System.in));
- int sticks = Integer.parseInt(buffReader.readLine());
- int stickPlacings = Integer.parseInt(buffReader.readLine());
- HashMap<Integer, Stick> allSticks = new HashMap<>();
- for (int i = 0; i < sticks; i++) {
- allSticks.put(i, new Stick(i));
- }
- //place sticks
- for (int i = 0; i < stickPlacings; i++) {
- int[] values = Arrays.stream(buffReader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
- int onTop = values[0];
- int below = values[1];
- Stick stickOnTop = allSticks.get(onTop);
- Stick stickBelow = allSticks.get(below);
- allSticks.get(below).addOnTop(stickOnTop);
- allSticks.get(onTop).addBelow(stickBelow);
- }
- for (int i = 0; i < sticks; i++) {
- Collections.sort(allSticks.get(i).below, (o1, o2) -> Integer.compare(o2.getValue(), o1.getValue()));
- }
- //lift
- Queue<Stick> stickQueue = new LinkedList<>();
- for (int i = sticks - 1; i > 0; i--) {
- Stick current = allSticks.get(i);
- if (current.onTop.size() == 0) {
- stickQueue.add(current);
- }
- }
- HashSet<Integer> results = new LinkedHashSet<>();
- boolean[] canBeLifted = new boolean[sticks];
- while (!stickQueue.isEmpty()) {
- Stick current = stickQueue.poll();
- if (current.onTop.size() == 0) {
- canBeLifted[current.getValue()] = true;
- results.add(current.getValue());
- }
- for (Stick stick : current.below) {
- if (!stick.onTop.contains(current)) {
- continue;
- }
- if (canBeLifted[current.getValue()]) {
- stick.onTop.remove(current);
- if (stickQueue.peek()== null || stickQueue.peek().getValue() != stick.getValue()) {
- stickQueue.add(stick);
- }
- }
- }
- }
- if (results.size() != sticks) {
- System.out.println("Cannot lift all sticks");
- }
- System.out.println(String.join(" ", results.stream().map(String::valueOf).collect(Collectors.toList())));
- }
- private static class Stick {
- private int value;
- private List<Stick> onTop;
- private List<Stick> below;
- private Stick(int value) {
- this.value = value;
- this.onTop = new LinkedList<>();
- this.below = new LinkedList<>();
- }
- public void addBelow(Stick stick) {
- this.below.add(stick);
- }
- public void addOnTop(Stick stick) {
- this.onTop.add(stick);
- }
- public int getValue() {
- return this.value;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement