Pagini recente » Cod sursa (job #2248137) | Cod sursa (job #146996) | Cod sursa (job #1957496) | Cod sursa (job #1517611) | Cod sursa (job #3266288)
import java.io.*;
import java.util.*;
public class Main {
public static class DirectGraph {
private List<Integer>[] adjList;
public DirectGraph(int n) {
adjList = (List<Integer>[]) new List[n+1];
}
public void addEdge(int u, int v) {
if (adjList[u] == null) {
adjList[u] = new LinkedList<>();
}
adjList[u].add(v);
}
public List<Integer> neighbors(int u) {
if (adjList[u] == null) {
return Collections.emptyList();
} else {
return adjList[u];
}
}
}
public static void topologicalSort(DirectGraph g, int u, Deque<Integer> stack, boolean[] visited) {
visited[u] = true;
List<Integer> neighbors = g.neighbors(u);
if (neighbors != null) {
for (int v : neighbors) {
if (!visited[v]) {
topologicalSort(g, v, stack, visited);
}
}
}
stack.push(u);
}
public static void main(String[] args) throws IOException {
try (BufferedReader reader = new BufferedReader(new FileReader("sortaret.in"));
PrintStream ps = new PrintStream(new FileOutputStream("sortaret.out"), true)) {
StringTokenizer st = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
DirectGraph g = new DirectGraph(N);
for (int i = 0; i < M; i++) {
st = new StringTokenizer(reader.readLine());
g.addEdge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
Deque<Integer> stack = new LinkedList<>();
boolean[] visited = new boolean[N+1];
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
topologicalSort(g, i, stack, visited);
}
}
for (int v : stack) {
ps.print(v);
ps.print(" ");
}
ps.println();
}
}
}