import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; import java.util.Stack; import java.util.Arrays; public class Toposort { private static ArrayList toposort(ArrayList> adj) { boolean[] visited = new boolean[adj.size()]; Integer[] postv = new Integer[adj.size()]; int[] clock = new int[1]; dfs(adj, visited, postv, clock); Integer[] reverse_postv = postv.clone(); Arrays.sort(reverse_postv, Collections.reverseOrder()); ArrayList order = new ArrayList<>(); for (int n : reverse_postv) { order.add(Arrays.asList(postv).indexOf(n)); } return order; } private static void dfs(ArrayList> adj, boolean[] visited, Integer[] postv, int[] clock) { for (int v = 0; v < adj.size(); v++) { if (visited[v] == false) explore(adj, v, visited, postv, clock); } } private static void explore(ArrayList> adj, int v, boolean[] visited, Integer[] postv, int[] clock) { visited[v] = true; clock[0] = clock[0] + 1; for (int n : adj.get(v)) { if (visited[n] == false) explore(adj, n, visited, postv, clock); } postv[v] = clock[0]; clock[0] = clock[0] + 1; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); ArrayList> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList()); } for (int i = 0; i < m; i++) { int x, y; x = scanner.nextInt(); y = scanner.nextInt(); adj.get(x - 1).add(y - 1); } ArrayList order = toposort(adj); for (int x : order) { System.out.print((x + 1) + " "); } } static ArrayList postOrder(ArrayList> adj) { boolean[] visited = new boolean[adj.size()]; ArrayList postv = new ArrayList<>(Collections.nCopies(adj.size(), 0)); int[] clock = new int[1]; clock[0] = clock[0] + 1; for (int v = 0; v < adj.size(); v++) { exploreIterative(adj, v, visited, postv, clock); } return postv; } private static void exploreIterative(ArrayList> adj, int v, boolean[] visited, ArrayList postv, int[] clock) { if (visited[v] == false) { // prev[v] = clock[0] boolean[] inStack = new boolean[adj.size()]; clock[0] = clock[0] + 1; visited[v] = true; inStack[v] = true; Stack vertexStack = new Stack<>(); vertexStack.push(v); while (vertexStack.isEmpty() == false) { int tempVertex = vertexStack.peek(); // if (tempVertex != v) { // visited[tempVertex] = true; // // prev[v] = clock[0] // clock[0] = clock[0] + 1; // } if (tempVertex != v && visited[tempVertex]) { vertexStack.pop(); continue; } if (adj.get(tempVertex).size() == 0) { if (tempVertex != v) { // prev[tempVertex] = clock[0]; clock[0] = clock[0] + 1; visited[tempVertex] = true; } postv.set(tempVertex, clock[0]); clock[0] = clock[0] + 1; vertexStack.pop(); } else { boolean allEdgesFollowed = true; for (int i : adj.get(tempVertex)) { if (visited[i] == false) { // visited[i] = true; // prev[i] = clock[0] if (inStack[i] == false) { inStack[i] = true; vertexStack.push(i); } allEdgesFollowed = false; } } if (allEdgesFollowed) { visited[tempVertex] = true; if (postv.get(tempVertex) == 0) postv.set(tempVertex, clock[0]); clock[0] = clock[0] + 1; vertexStack.pop(); } } } } } }