Pagini recente » Cod sursa (job #1622226) | Borderou de evaluare (job #72812) | Atasamentele paginii Profil dangabriel | Borderou de evaluare (job #2764042) | Cod sursa (job #1363300)
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
class Graph {
private List<List<Integer>> adj;
private Map<Integer, Integer> map;
private Map<Integer, Integer> ord;
private int value;
Graph(List<List<Integer>> adj) {
this.adj = adj;
}
List<Integer> topoSort() {
int N = adj.size();
map = new HashMap<Integer, Integer>(N);
ord = new HashMap<Integer, Integer>(N);
value = 0;
for (int node = 0; node < N; ++node) {
topoSort(node);
}
List<Integer> values = new ArrayList<Integer>(N);
for (int node = 0; node < N; ++node) {
values.add(1 + ord.get(node));
}
return values;
}
private void topoSort(int node) {
if (map.containsKey(node)) {
return;
}
List<Integer> siblings = adj.get(node);
for (int sibling : siblings) {
topoSort(sibling);
}
ord.put(value, node);
map.put(node, value++);
}
}
public class Main {
public static void main(String[] args) throws IOException {
InputStream inputStream = new FileInputStream("sortaret.in");
Scanner scanner = new Scanner(inputStream);
OutputStream outputStream = new FileOutputStream("sortaret.out");
PrintWriter writer = new PrintWriter(outputStream);
int N = scanner.nextInt();
int M = scanner.nextInt();
List<List<Integer>> adj = new ArrayList<List<Integer>>(N);
for (int i = 0; i < N; ++i) {
adj.add(new ArrayList<Integer>());
}
while (M-- > 0) {
int x = scanner.nextInt() - 1;
int y = scanner.nextInt() - 1;
adj.get(y).add(x);
}
Graph graph = new Graph(adj);
List<Integer> topoSort = graph.topoSort();
for (int node : topoSort) {
writer.print(node);
writer.print(" ");
}
writer.flush();
inputStream.close();
scanner.close();
outputStream.close();
writer.close();
}
}