Pagini recente » Cod sursa (job #2950745) | Cod sursa (job #2934197) | Cod sursa (job #2861294) | Cod sursa (job #254495) | Cod sursa (job #3242336)
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.Stack;
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);
}
Stack<Integer> nodes = graph.topologicalSorting();
while (!nodes.isEmpty()) {
writer.print(nodes.pop() + " ");
}
}
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 Stack<Integer> topologicalSorting() {
boolean[] visited = new boolean[n + 1];
Stack<Integer> stack = new Stack<>();
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
dfs(i, visited, stack);
}
}
return stack;
}
private void dfs(int fromNode, boolean[] visited, Stack<Integer> stack) {
visited[fromNode] = true;
this.links.get(fromNode).forEach(toNode -> {
if (!visited[toNode]) {
dfs(toNode, visited, stack);
}
});
stack.push(fromNode);
}
}
}