Advertisement
Guest User

Untitled

a guest
Aug 29th, 2016
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.09 KB | None | 0 0
  1.  
  2. import java.io.BufferedReader;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.util.*;
  6.  
  7. public class SticksTopologicalSorting {
  8.  
  9.     public static void main(String[] args) throws IOException {
  10.         BufferedReader buffReader = new BufferedReader(new InputStreamReader(System.in));
  11.         int stickCount = Integer.valueOf(buffReader.readLine());
  12.         int stickPlacings = Integer.valueOf(buffReader.readLine());
  13.  
  14.         HashMap<Integer, List<Integer>> graph = new HashMap<>();
  15.         for (int i = 0; i < stickCount; i++) {
  16.             graph.put(i, new LinkedList<>());
  17.         }
  18.         int[] predecessorsCount = new int[graph.size()];
  19.         for (int i = 0; i < stickPlacings; i++) {
  20.             String[] sticks = buffReader.readLine().split("\\s+");
  21.             int topStick = Integer.valueOf(sticks[0]);
  22.             int bottomStick = Integer.valueOf(sticks[1]);
  23.             graph.get(topStick).add(bottomStick);
  24.         }
  25.         for (int stick = 0; stick < graph.size(); stick++) {
  26.             for (int bottomStick : graph.get(stick)) {
  27.                 predecessorsCount[bottomStick]++;
  28.             }
  29.         }
  30.         boolean[] isRemoved = new boolean[graph.size()];
  31.         Queue<Integer> liftedSticks = new LinkedList<>();
  32.         boolean stickRemoved = true;
  33.         while (stickRemoved) {
  34.             stickRemoved = false;
  35.             for (int stick = graph.size() - 1; stick >= 0; stick--) {
  36.                 if (predecessorsCount[stick] == 0 && !isRemoved[stick]) {
  37.                     for (int bottomStick : graph.get(stick)) {
  38.                         predecessorsCount[bottomStick]--;
  39.                     }
  40.                     isRemoved[stick] = true;
  41.                     stickRemoved = true;
  42.                     liftedSticks.add(stick);
  43.                     break;
  44.                 }
  45.             }
  46.         }
  47.         if (liftedSticks.size() < graph.size()) {
  48.             System.out.println("Cannot lift all sticks");
  49.         }
  50.  
  51.         while (!liftedSticks.isEmpty()) {
  52.             System.out.print(liftedSticks.poll() + " ");
  53.         }
  54.     }
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement