Pagini recente » Cod sursa (job #3283353) | Cod sursa (job #461446) | b0$$ de b0$$ | Cod sursa (job #1515814) | Cod sursa (job #1792051)
//package topo_sort;
import java.io.*;
import java.util.*;
/**
* Created on 29.10.2016.
*/
class Node {
private int value;
private List<Node> adjacent;
Node(int value) {
this.value = value;
adjacent = new ArrayList<>();
}
List<Node> getAdjacent() {
return adjacent;
}
void addAdjacent(Node node) {
adjacent.add(node);
}
int getValue() {
return value;
}
}
class Graph {
private List<Node> vertices;
Graph(int size) {
vertices = new ArrayList<>();
for (int i = 0; i < size; i++) {
vertices.add(new Node(i + 1));
}
}
void dfs(Node current, Set<Node> visited, Stack<Node> stack) {
visited.add(current);
for (Node adj : current.getAdjacent()) {
if (!visited.contains(adj)) {
dfs(adj, visited, stack);
}
}
stack.add(current);
}
void addEdge(int x, int y) {
vertices.get(x - 1).addAdjacent(vertices.get(y - 1));
}
List<Node> getVertices() {
return vertices;
}
}
public class Main {
public static void main(String[] args) throws IOException {
InputReader reader = new InputReader("sortaret.in");
BufferedWriter writer = new BufferedWriter(new FileWriter("sortaret.out"));
Graph graph = readInput(reader);
List<Integer> results = solveTask(graph);
writeResults(writer, results);
writer.close();
}
private static Graph readInput(InputReader reader) {
int noOfVertices = reader.nextInt(),
noOfEdges = reader.nextInt();
Graph graph = new Graph(noOfVertices);
for (int i = 0; i < noOfEdges; i++) {
graph.addEdge(reader.nextInt(), reader.nextInt());
}
return graph;
}
private static List<Integer> solveTask(Graph graph) {
Set<Node> visited = new HashSet<>();
Stack<Node> stack = new Stack<>();
for (Node node : graph.getVertices()) {
if (!visited.contains(node)) {
graph.dfs(node, visited, stack);
}
}
List<Integer> results = new ArrayList<>();
while (!stack.isEmpty()) {
results.add(stack.pop().getValue());
}
return results;
}
private static void writeResults(Writer writer, List<Integer> results) throws IOException {
for (Integer vertex : results) {
writer.write(vertex + " ");
}
}
private static class InputReader {
BufferedReader reader;
StringTokenizer tokenizer;
InputReader(String fileName) throws FileNotFoundException {
reader = new BufferedReader(new FileReader(fileName), 32768);
tokenizer = null;
}
String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}