Pagini recente » Cod sursa (job #3281765) | Cod sursa (job #3183204) | Cod sursa (job #427670) | Cod sursa (job #3279213) | Cod sursa (job #2237422)
import static java.util.Objects.requireNonNull;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.List;
public final class Main {
public static final String IN_FILE = "sortaret.in";
public static final String OUT_FILE = "sortaret.out";
public static final class FastScanner implements AutoCloseable {
private final BufferedReader reader;
private StringTokenizer tokenizer;
public FastScanner(final String fileName) throws IOException {
reader = new BufferedReader(
new InputStreamReader(new FileInputStream(fileName)));
}
private String next() throws IOException {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
final String line = requireNonNull(reader.readLine());
tokenizer = new StringTokenizer(line);
}
return tokenizer.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
@Override
public void close() throws IOException {
reader.close();
}
}
public static void dfs(
final int[][] graph,
final int u,
final boolean[] visited,
final List<Integer> order) {
visited[u] = true;
for (final int v : graph[u]) {
if (!visited[v]) {
dfs(graph, v, visited, order);
}
}
order.add(u);
}
public static int[] getTopologicalOrder(final int[][] graph) {
final List<Integer> order = new ArrayList<>();
final boolean[] visited = new boolean[graph.length];
for (int u = 0; u < graph.length; u++) {
if (!visited[u]) {
dfs(graph, u, visited, order);
}
}
Collections.reverse(order);
return order.stream().mapToInt(Integer::intValue).toArray();
}
public static int[][] readGraph(final FastScanner scanner)
throws IOException {
final int size = scanner.nextInt();
final int edgeCount = scanner.nextInt();
final int[][] edges = new int[edgeCount][];
final int[] degrees = new int[size];
for (int e = 0; e < edgeCount; e++) {
final int u = scanner.nextInt() - 1;
final int v = scanner.nextInt() - 1;
edges[e] = new int[] {u, v};
degrees[u]++;
}
final int[][] graph = new int[size][];
for (int u = 0; u < size; u++) {
graph[u] = new int[degrees[u]];
}
for (int e = 0; e < edgeCount; e++) {
final int u = edges[e][0];
final int v = edges[e][1];
graph[u][degrees[u] - 1] = v;
degrees[u]--;
}
return graph;
}
public static void main(final String[] args) throws IOException {
try (final FastScanner scanner = new FastScanner(IN_FILE);
final PrintWriter writer = new PrintWriter(OUT_FILE)) {
final int[][] graph = readGraph(scanner);
final int[] order = getTopologicalOrder(graph);
for (int i = 0; i < order.length; i++) {
writer.print(order[i]);
writer.print(i + 1 < order.length ? ' ' : '\n');
}
}
}
}