Cod sursa(job #1870035)

Utilizator preda.andreiPreda Andrei preda.andrei Data 6 februarie 2017 12:20:08
Problema Sortare topologica Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 3.53 kb
import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        Reader in = new Reader(new FileInputStream("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);
        }

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

    private static class Reader {
        private BufferedInputStream stream;
        private byte[] buffer;
        int buffSize;
        private int buffPointer;

        protected final int BUFF_CAPACITY = 5000;

        protected Reader(FileInputStream file) {
            stream = new BufferedInputStream(file);
            buffer = new byte[BUFF_CAPACITY];
            buffPointer = buffSize = 0;
        }

        private void fillBuffer() throws IOException {
            buffSize = stream.read(buffer, 0, BUFF_CAPACITY);
            buffPointer = 0;
        }

        private byte readByte() throws IOException {
            if (buffPointer >= buffSize) {
                fillBuffer();
            }
            return buffer[buffPointer++];
        }

        protected int nextInt() throws IOException {
            byte b = readByte();
            while (b < '0' || b > '9') {
                b = readByte();
            }

            int num = 0;
            while (b >= '0' && b <= '9') {
                num = num * 10 + (b - '0');
                b = readByte();
            }
            return num;
        }
    }
}

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 edges;
        }

        public boolean wasVisited() {
            return visited;
        }

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