Pagini recente » Cod sursa (job #235535) | Cod sursa (job #2991138) | Monitorul de evaluare | Cod sursa (job #3222836) | Cod sursa (job #2238844)
import static java.lang.Character.isDigit;
import static java.util.Arrays.copyOf;
import static java.util.Arrays.fill;
import static java.util.Objects.requireNonNull;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintWriter;
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 static final int BUFFER_SIZE = 1 << 16;
private final DataInputStream stream;
private final byte[] buffer = new byte[BUFFER_SIZE];
private int bufferPointer = 0;
private int bytesRead = 0;
public FastScanner(final String fileName) throws IOException {
stream = new DataInputStream(new FileInputStream(fileName));
}
public int nextInt() throws IOException {
byte c;
do {
c = read();
} while (c != '-' && !isDigit(c));
final boolean isNegative = c == '-';
if (isNegative) {
c = read();
}
int value = 0;
do {
value = value * 10 + (c - '0');
c = read();
} while (isDigit(c));
return isNegative ? -value : value;
}
private byte read() throws IOException {
final byte c = tryRead();
if (c == -1) {
throw new IOException("Reached end of stream!");
}
return c;
}
private byte tryRead() throws IOException {
if (bufferPointer == bytesRead) {
bufferPointer = 0;
bytesRead = stream.read(buffer, 0, BUFFER_SIZE);
if (bytesRead == -1) {
bytesRead = 0;
return -1;
}
}
return buffer[bufferPointer++];
}
@Override
public void close() throws IOException {
stream.close();
}
}
public static final class Graph {
private final int[][] graph;
private final boolean[] visited;
private final int[] order;
private int position;
public Graph(
final int size, final int edges, final int[] us, final int[] vs) {
final int[] degrees = new int[size];
for (int e = 0; e < edges; e++) {
degrees[us[e]]++;
}
graph = new int[size][];
for (int u = 0; u < size; u++) {
graph[u] = new int[degrees[u]];
}
for (int e = 0; e < edges; e++) {
final int u = us[e];
final int v = vs[e];
graph[u][degrees[u] - 1] = v;
degrees[u]--;
}
visited = new boolean[size];
order = new int[size];
position = 0;
}
public int[] getTopologicalOrder() {
fill(visited, false);
position = 0;
for (int u = 0; u < graph.length; u++) {
if (!visited[u]) {
dfs(u);
}
}
reverse(order);
return copyOf(order, position);
}
private static void reverse(final int[] values) {
for (int i = 0, j = values.length - 1; i < j; i++, j--) {
final int tmp = values[i];
values[i] = values[j];
values[j] = tmp;
}
}
private void dfs(final int u) {
visited[u] = true;
for (final int v : graph[u]) {
if (!visited[v]) {
dfs(v);
}
}
order[position++] = u;
}
}
public static Graph readGraph(final FastScanner scanner) throws IOException {
final int size = scanner.nextInt();
final int edges = scanner.nextInt();
final int[] us = new int[edges];
final int[] vs = new int[edges];
for (int e = 0; e < edges; e++) {
us[e] = scanner.nextInt() - 1;
vs[e] = scanner.nextInt() - 1;
}
return new Graph(size, edges, us, vs);
}
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 Graph graph = readGraph(scanner);
final int[] order = graph.getTopologicalOrder();
for (int i = 0; i < order.length; i++) {
writer.print(order[i] + 1);
writer.print(i + 1 < order.length ? ' ' : '\n');
}
}
}
}