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.*;
- public class SticksTopologicalSorting {
- static boolean[] visited;
- static HashMap<Integer, List<Integer>> stickMap = new HashMap<>();
- static LinkedList<Integer> results = new LinkedList<>();
- static HashSet<Integer> currentVisited = new HashSet<>();
- static boolean[] hasOnTop;
- public static void main(String[] args) throws IOException {
- BufferedReader buffReader = new BufferedReader(new InputStreamReader(System.in));
- int sticks = Integer.parseInt(buffReader.readLine());
- int placings = Integer.parseInt(buffReader.readLine());
- visited = new boolean[sticks];
- hasOnTop = new boolean[sticks];
- for (int i = 0; i < sticks; i++) {
- stickMap.put(i, new LinkedList<>());
- }
- for (int i = 0; i < placings; i++) {
- String[] params = buffReader.readLine().split(" ");
- int parent = Integer.parseInt(params[0]);
- int child = Integer.parseInt(params[1]);
- stickMap.get(parent).add(child);
- hasOnTop[child] = true;
- }
- List<Integer> start = new LinkedList<>();
- for (int i = 0; i < sticks; i++) {
- if (!hasOnTop[i]) {
- start.add(i);
- }
- }
- for (int num : start) {
- try {
- topSortDfs(num, num);
- } catch (IllegalArgumentException ex) {
- }
- }
- if (results.size() < sticks) {
- System.out.println("Cannot lift all sticks");
- }
- for (int liftedStick : results) {
- System.out.print(liftedStick + " ");
- }
- }
- private static void topSortDfs(int starter, int vertex) {
- if (currentVisited.contains(vertex)) {
- results.addFirst(starter);
- throw new IllegalArgumentException();
- }
- if (!visited[vertex]) {
- currentVisited.add(vertex);
- visited[vertex] = true;
- List<Integer> children = stickMap.get(vertex);
- for (int child : children) {
- topSortDfs(starter, child);
- }
- results.addFirst(vertex);
- currentVisited.remove(vertex);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement