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 {
- public static void main(String[] args) throws IOException {
- BufferedReader buffReader = new BufferedReader(new InputStreamReader(System.in));
- int stickCount = Integer.valueOf(buffReader.readLine());
- int stickPlacings = Integer.valueOf(buffReader.readLine());
- HashMap<Integer, List<Integer>> graph = new HashMap<>();
- for (int i = 0; i < stickCount; i++) {
- graph.put(i, new LinkedList<>());
- }
- int[] predecessorsCount = new int[graph.size()];
- for (int i = 0; i < stickPlacings; i++) {
- String[] sticks = buffReader.readLine().split("\\s+");
- int topStick = Integer.valueOf(sticks[0]);
- int bottomStick = Integer.valueOf(sticks[1]);
- graph.get(topStick).add(bottomStick);
- }
- for (int stick = 0; stick < graph.size(); stick++) {
- for (int bottomStick : graph.get(stick)) {
- predecessorsCount[bottomStick]++;
- }
- }
- boolean[] isRemoved = new boolean[graph.size()];
- Queue<Integer> liftedSticks = new LinkedList<>();
- boolean stickRemoved = true;
- while (stickRemoved) {
- stickRemoved = false;
- for (int stick = graph.size() - 1; stick >= 0; stick--) {
- if (predecessorsCount[stick] == 0 && !isRemoved[stick]) {
- for (int bottomStick : graph.get(stick)) {
- predecessorsCount[bottomStick]--;
- }
- isRemoved[stick] = true;
- stickRemoved = true;
- liftedSticks.add(stick);
- break;
- }
- }
- }
- if (liftedSticks.size() < graph.size()) {
- System.out.println("Cannot lift all sticks");
- }
- while (!liftedSticks.isEmpty()) {
- System.out.print(liftedSticks.poll() + " ");
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement