Cod sursa(job #1869959)

Utilizator preda.andreiPreda Andrei preda.andrei Data 6 februarie 2017 11:42:00
Problema Sortare topologica Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 2.4 kb
import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(new FileReader("sortaret.in"));
        int n = in.nextInt(), m = in.nextInt();
        Graph graph = new Graph(n);

        for (int i = 0; i < m; ++i) {
           int x = in.nextInt(), y = in.nextInt();
           graph.addEdge(x - 1, y - 1);
        }
        in.close();

        List<Integer> sorted = TopologicalSort.topSort(graph);
        FileWriter out = new FileWriter("sortaret.out");
        for (int i : sorted) {
           out.write((i + 1) +  " ");
        }
        out.close();
    }
}

class TopologicalSort {
    public static List<Integer> topSort(Graph g) {
        int n = g.numberOfNodes();
        List<Integer> sorted = new ArrayList<Integer>(n);

        for (int i = 0; i < n; ++i) {
            if (!g.getNode(i).wasVisited()) {
                Dfs(g, i, sorted);
            }
        }

        Collections.reverse(sorted);
        return sorted;
    }

    private static void Dfs(Graph g, int node, List<Integer> sorted) {
        g.getNode(node).setVisited(true);
        for (int neighbour : g.getNode(node).getEdges()) {
            if (!g.getNode(neighbour).wasVisited()) {
                Dfs(g, neighbour, sorted);
            }
        }
        sorted.add(node);
    }
}

class Graph {

    private List<Node> nodes;

    public Graph(int n) {
        nodes = new ArrayList<Node>(n);
        for (int i = 0; i < n; ++i) {
            nodes.add(new Node());
        }
    }

    public void addEdge(int x, int y) {
        nodes.get(x).addEdge(y);
    }

    public int numberOfNodes() {
        return nodes.size();
    }

    public Node getNode(int i) {
        return nodes.get(i);
    }

    protected static class Node {
        private boolean visited;
        private List<Integer> edges;

        public Node() {
            visited = false;
            edges = new ArrayList<Integer>();
        }

        public void addEdge(int neighbour) {
            edges.add(neighbour);
        }

        public List<Integer> getEdges() {
            return Collections.unmodifiableList(edges);
        }

        public boolean wasVisited() {
            return visited;
        }

        public void setVisited(boolean b) {
            visited = b;
        }
    }
}