Cod sursa(job #1369196)

Utilizator stefan.vascoVanea Stefan Vascocenco stefan.vasco Data 2 martie 2015 22:32:25
Problema Sortare topologica Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.3 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 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());

    }

}