Pagini recente » Cod sursa (job #1392013) | Cod sursa (job #268301) | Cod sursa (job #2924053) | Monitorul de evaluare | Cod sursa (job #3266291)
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 int head = 0;
public static void topologicalSort(DirectGraph g, int u, boolean[] visited, int[] stack) {
visited[u] = true;
List<Integer> neighbors = g.neighbors(u);
if (neighbors != null) {
for (int v : neighbors) {
if (!visited[v]) {
topologicalSort(g, v, visited, stack);
}
}
}
// stack.push(u);
stack[head] = u;
head++;
}
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];
int[] deque = new int[N+1];
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
topologicalSort(g, i, visited, deque);
}
}
while (head > 0) {
head--;
ps.print(deque[head]);
ps.print(" ");
}
ps.println();
// for (int v : stack) {
// ps.print(v);
// ps.print(" ");
// }
// ps.println();
}
}
}