Pagini recente » Cod sursa (job #2780898) | Cod sursa (job #3004444) | Cod sursa (job #2852616) | Cod sursa (job #1081143) | Cod sursa (job #2146444)
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.FileNotFoundException;
public class Main {
public static void main(String[] args) throws FileNotFoundException, IOException {
InputStream inputStream = new FileInputStream(new File("./sortaret.in"));
OutputStream outputStream = new FileOutputStream(new File("./sortaret.out"));
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task solver = new Task();
solver.solve(in, out);
out.close();
}
static class Task{
static final int INF = (int) 1.01e9;
public void solve(InputReader in, PrintWriter out){
int numberOfNodes = in.nextInt();
int numberOfEdges = in.nextInt();
// construct the graph
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < numberOfEdges; i++) {
int source = in.nextInt();
int destination = in.nextInt();
if (graph.containsKey(source)) {
List<Integer> adjList = graph.get(source);
adjList.add(destination);
graph.put(source, adjList);
}
else {
List<Integer> adjList = new ArrayList<>();
adjList.add(destination);
graph.put(source, adjList);
}
}
List<Integer> result = topologicalSort(graph, numberOfNodes);
for (int i = result.size() - 1; i>= 0; i--) {
out.write(result.get(i).toString());
//System.out.print(" ");
}
}
public void dfs(int startNode, Map<Integer, List<Integer>> graph,
Set<Integer> visited, List<Integer> result) {
if (!graph.containsKey(startNode)) {
visited.add(startNode);
result.add(startNode);
return;
}
visited.add(startNode);
for (int neighbour : graph.get(startNode)) {
if (!visited.contains(neighbour)) {
dfs(neighbour, graph, visited, result);
}
}
result.add(startNode);
}
public List<Integer> topologicalSort(Map<Integer, List<Integer>> graph,
int noOfNodes) {
List<Integer> result = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
for (int node = 1; node <= noOfNodes; node++) {
if (!visited.contains(node)) {
dfs(node, graph, visited, result);
}
}
return result;
}
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
}