Pagini recente » Infoarena Monthly 2014 - Solutii Runda 5 | Cod sursa (job #1566791) | Cod sursa (job #671340) | Cod sursa (job #2269069) | Cod sursa (job #1792023)
//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 TopologicalSort {
public static void main(String[] args) throws IOException {
Scanner reader = new Scanner(new FileReader("sortaret.in"));
BufferedWriter writer = new BufferedWriter(new FileWriter("sortaret.out"));
Graph graph = readInput(reader);
List<Integer> results = solveTask(graph);
writeResults(results, writer);
reader.close();
writer.close();
}
private static Graph readInput(Scanner 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(List<Integer> results, Writer writer) throws IOException {
for (Integer vertex : results) {
writer.write(vertex + " ");
}
}
}