import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.PriorityQueue; import java.util.stream.Collectors; public class TopologicalSort { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int verticesCount = Integer.parseInt(reader.readLine()); int edgesCount = Integer.parseInt(reader.readLine()); ArrayList> adjList = new ArrayList<>(verticesCount); for (int i = 0; i < verticesCount; i++) { adjList.add(new ArrayList()); } for (int i = 0; i < edgesCount; i++) { String[] splitParams = reader.readLine().split(" "); int parent = Integer.parseInt(splitParams[0]); int child = Integer.parseInt(splitParams[1]); adjList.get(parent).add(child); } // Create an array to store indegrees of all vertices // Initialize all indegrees to 0 ArrayList inDegree = new ArrayList<>(verticesCount); for (int i = 0; i < verticesCount; i++) { inDegree.add(0); } // Traverse adjacency list to fill indegrees of vertices for (int u = 0; u < verticesCount; u++) { for (int i = 0; i < adjList.get(u).size(); i++) { int index = adjList.get(u).get(i); inDegree.set(index, inDegree.get(index) + 1); } } // Add all vertices with inDegree == 0 PriorityQueue pq = new PriorityQueue<>(); for (var i = 0; i < verticesCount; i++) { if (inDegree.get(i) == 0) { pq.add(i); } } // Create a collection to store the result (A topological ordering of the vertices) ArrayList topoplogicalOrder = new ArrayList<>(verticesCount); // remove next smallest vertex from min heap/priority queue // reduce indegree of children // add children with indegree == 0 to min heap/priority queue while (pq.size() > 0) { // Extract vertex with minimum number from min heap/priority queue // and add it to topological order int u = pq.poll(); topoplogicalOrder.add(u); // Iterate through all children of vertex and reduce their in-degree by 1 for (var i = 0; i < adjList.get(u).size(); i++) { // If in-degree becomes zero, add it to min heap/priority queue int index = adjList.get(u).get(i); inDegree.set(index, inDegree.get(index) - 1); if (inDegree.get(index) == 0) pq.add(index); } } // Check if there was a cycle if (topoplogicalOrder.size() != verticesCount) { System.out.println("circular dependency"); } else { String joined = topoplogicalOrder.stream() .map(Object::toString) .collect(Collectors.joining(" ")); System.out.println(joined); } } }