Cod sursa(job #1369763)

Utilizator stefan.vascoVanea Stefan Vascocenco stefan.vasco Data 3 martie 2015 11:13:49
Problema Sortare topologica Scor 40
Compilator java Status done
Runda Arhiva educationala Marime 2.64 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;
    private int finishTime;
    
    public Sortp() {
        graph = new HashMap<Integer, LinkedList<Integer>>();
    }
    
    public Sortp(int vertexCount) {
        graph = new HashMap<Integer, LinkedList<Integer>>();
        for (; vertexCount > 0; vertexCount--) {
            graph.put(vertexCount, new LinkedList<Integer>());
        }
    }
    
    public void addEdge(int nodeA, int nodeB) {
        graph.get(nodeA).add(nodeB);
    }
    
    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 (!sorted.contains(node.getKey())) {
                DFS(node.getKey(), sorted, visited);
            }
        }
        
        return sorted;
    }
    
    private void DFS(int currentNode, LinkedList<Integer> sorted, LinkedList<Integer> visited) {
        if (visited.contains(currentNode)) {
            visited.add(currentNode);
        }
        for (int inNode : graph.get(currentNode)) {
            if (!visited.contains(inNode)) {
                DFS(inNode, sorted, visited);
            }
        }
        if (!sorted.contains(currentNode)) {
            sorted.addFirst(currentNode);
        }
    }
    
}

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 {
        try (Scanner sc = new Scanner(new FileInputStream("sortaret.in"))) {
            int vertexCount = sc.nextInt();
            int edgeCount = sc.nextInt();
            Sortp sortp = new Sortp(vertexCount);
            
            for (; edgeCount > 0; edgeCount--) {
                sortp.addEdge(sc.nextInt(), sc.nextInt());
            }
            sc.close();
            writeOutput(sortp.execDFSSort());
        }
    }
    
}