Pagini recente » Profil Mihaela_Narita | Cod sursa (job #1672649) | Cod sursa (job #1401714) | Cod sursa (job #1981868) | Cod sursa (job #1369196)
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;
private HashMap<Integer, Integer> indeg;
public Sortp() {
graph = new HashMap<Integer, LinkedList<Integer>>();
indeg = new HashMap<Integer, Integer>();
}
public void addEdge(int nodeA, int nodeB) {
if (!graph.containsKey(nodeA)) {
graph.put(nodeA, new LinkedList<Integer>());
indeg.put(nodeA, 0);
}
if (!graph.containsKey(nodeB)) {
graph.put(nodeB, new LinkedList<Integer>());
indeg.put(nodeB, 0);
}
graph.get(nodeA).add(nodeB);
indeg.put(nodeB, indeg.get(nodeB) + 1);
}
public LinkedList<Integer> execSort() {
LinkedList<Integer> sorted = new LinkedList<Integer>();
LinkedList<Integer> queue = new LinkedList<Integer>();
for (Map.Entry<Integer, LinkedList<Integer>> node : graph.entrySet()) {
if (indeg.get(node.getKey()) == 0) {
queue.add(node.getKey());
}
}
while (queue.size() > 0) {
int currentNode = queue.poll();
sorted.add(currentNode);
for (int inNode : graph.get(currentNode)) {
if (indeg.get(inNode) > 0) {
indeg.put(inNode, indeg.get(inNode) - 1);
if (indeg.get(inNode) == 0) {
queue.addLast(inNode);
}
}
}
}
return sorted;
}
public LinkedList<Integer> execDFSSort() {
LinkedList<Integer> sorted = new LinkedList<Integer>();
LinkedList<Integer> visited = new LinkedList<Integer>();
for (Map.Entry<Integer, LinkedList<Integer>> node : graph.entrySet()) {
if (!visited.contains(node.getKey())) {
DFS(node.getKey(), sorted);
}
}
return sorted;
}
private void DFS(int currentNode, LinkedList<Integer> sorted) {
if (!sorted.contains(currentNode)) {
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.flush();
pr.close();
} catch (FileNotFoundException ex) {
ex.printStackTrace();
}
}
public static void main(String[] args) throws FileNotFoundException {
Sortp sortp = new Sortp();
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());
}
//writeOutput(sortp.execSort());
writeOutput(sortp.execDFSSort());
}
}