Advertisement
Guest User

Untitled

a guest
Aug 27th, 2016
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.33 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.*;
  5.  
  6. public class SticksTopologicalSorting {
  7.  
  8.     static boolean[] visited;
  9.     static HashMap<Integer, List<Integer>> stickMap = new HashMap<>();
  10.     static LinkedList<Integer> results = new LinkedList<>();
  11.     static HashSet<Integer> currentVisited = new HashSet<>();
  12.     static boolean[] hasOnTop;
  13.  
  14.     public static void main(String[] args) throws IOException {
  15.  
  16.         BufferedReader buffReader = new BufferedReader(new InputStreamReader(System.in));
  17.         int sticks = Integer.parseInt(buffReader.readLine());
  18.         int placings = Integer.parseInt(buffReader.readLine());
  19.         visited = new boolean[sticks];
  20.         hasOnTop = new boolean[sticks];
  21.         for (int i = 0; i < sticks; i++) {
  22.             stickMap.put(i, new LinkedList<>());
  23.         }
  24.         for (int i = 0; i < placings; i++) {
  25.             String[] params = buffReader.readLine().split(" ");
  26.             int parent = Integer.parseInt(params[0]);
  27.             int child = Integer.parseInt(params[1]);
  28.             stickMap.get(parent).add(child);
  29.             hasOnTop[child] = true;
  30.         }
  31.         List<Integer> start = new LinkedList<>();
  32.         for (int i = 0; i < sticks; i++) {
  33.             if (!hasOnTop[i]) {
  34.                 start.add(i);
  35.             }
  36.         }
  37.  
  38.         for (int num : start) {
  39.             try {
  40.                 topSortDfs(num, num);
  41.             } catch (IllegalArgumentException ex) {
  42.  
  43.             }
  44.         }
  45.         if (results.size() < sticks) {
  46.             System.out.println("Cannot lift all sticks");
  47.         }
  48.         for (int liftedStick : results) {
  49.             System.out.print(liftedStick + " ");
  50.         }
  51.     }
  52.  
  53.     private static void topSortDfs(int starter, int vertex) {
  54.         if (currentVisited.contains(vertex)) {
  55.             results.addFirst(starter);
  56.             throw new IllegalArgumentException();
  57.         }
  58.         if (!visited[vertex]) {
  59.             currentVisited.add(vertex);
  60.             visited[vertex] = true;
  61.             List<Integer> children = stickMap.get(vertex);
  62.  
  63.             for (int child : children) {
  64.                 topSortDfs(starter, child);
  65.             }
  66.             results.addFirst(vertex);
  67.  
  68.             currentVisited.remove(vertex);
  69.         }
  70.     }
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement