Mai intai trebuie sa te autentifici.
Cod sursa(job #1369332)
Utilizator | Data | 2 martie 2015 23:48:50 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 0 |
Compilator | java | Status | done |
Runda | Arhiva educationala | Marime | 2.17 kb |
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Scanner;
class Sortp {
private HashMap<Integer, LinkedList<Integer>> graph;
public Sortp() {
graph = new HashMap<Integer, LinkedList<Integer>>();
}
public void addEdge(int nodeA, int nodeB) {
if (!graph.containsKey(nodeA)) {
graph.put(nodeA, new LinkedList<Integer>());
}
if (!graph.containsKey(nodeB)) {
graph.put(nodeB, new LinkedList<Integer>());
}
graph.get(nodeA).add(nodeB);
}
public LinkedList<Integer> execDFSSort() {
LinkedList<Integer> sorted = new LinkedList<Integer>();
for (Map.Entry<Integer, LinkedList<Integer>> node : graph.entrySet()) {
if (!sorted.contains(node.getKey())) {
DFS(node.getKey(), sorted);
}
}
return sorted;
}
private void DFS(int currentNode, LinkedList<Integer> sorted) {
sorted.add(currentNode);
for (int inNode : graph.get(currentNode)) {
DFS(inNode, sorted);
}
}
}
public class Main {
private static void writeOutput(LinkedList<Integer> topsort) {
try {
PrintWriter pr = new PrintWriter("sortaret.out");
for (int vertex : topsort) {
pr.write(vertex + " ");
}
pr.write("\n");
pr.flush();
pr.close();
} catch (FileNotFoundException ex) {
ex.printStackTrace();
}
}
public static void main(String[] args) throws FileNotFoundException {
Sortp sortp = new Sortp();
try (Scanner sc = new Scanner(new FileInputStream("sortaret.in"))) {
int vertexCount = sc.nextInt();
int edgeCount = sc.nextInt();
for (; edgeCount > 0; edgeCount--) {
sortp.addEdge(sc.nextInt(), sc.nextInt());
}
sc.close();
}
writeOutput(sortp.execDFSSort());
}
}