Pagini recente » Cod sursa (job #2429938) | Cod sursa (job #1000198) | Cod sursa (job #2743142) | Cod sursa (job #18518) | Cod sursa (job #3242340)
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static final String INPUT_FILE = "sortaret.in";
static final String OUTPUT_FILE = "sortaret.out";
public static class TokenizedReader {
private final BufferedReader reader;
private StringTokenizer tokenizer;
TokenizedReader(String filePath) throws FileNotFoundException {
reader = new BufferedReader(new FileReader(filePath));
}
private String nextToken() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
private int nextInt() {
return Integer.parseInt(nextToken());
}
public void close() throws IOException {
reader.close();
}
}
public static void main(String[] args) throws IOException {
TokenizedReader reader = new TokenizedReader(INPUT_FILE);
PrintWriter writer = new PrintWriter(OUTPUT_FILE);
solve(reader, writer);
reader.close();
writer.flush();
writer.close();
}
public static void solve(TokenizedReader reader,
PrintWriter writer) {
int n = reader.nextInt();
int m = reader.nextInt();
DirectedGraph graph = new DirectedGraph(n);
while (m-- > 0) {
int from = reader.nextInt();
int to = reader.nextInt();
graph.link(from, to);
}
int[] nodes = graph.topologicalSorting();
for (int i = nodes[0]; i > 0; --i) {
writer.print(nodes[i] + " ");
}
}
public static class DirectedGraph {
public int n;
public List<List<Integer>> links;
public DirectedGraph(int n) {
this.n = n;
this.links = new ArrayList<>();
for (int i = 0; i <= n; ++i) {
this.links.add(new ArrayList<>());
}
}
public void link(int from, int to) {
this.links.get(from).add(to);
}
public int[] topologicalSorting() {
boolean[] visited = new boolean[n + 1];
int[] stack = new int[50000];
stack[0] = 0;
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
dfs(i, visited, stack);
}
}
return stack;
}
private void dfs(int fromNode, boolean[] visited, int[] stack) {
visited[fromNode] = true;
for (int toNode : this.links.get(fromNode)) {
if (!visited[toNode]) {
dfs(toNode, visited, stack);
}
}
stack[++stack[0]] = fromNode;
}
}
}