Cod sursa(job #2225841)

Utilizator radustn92Radu Stancu radustn92 Data 28 iulie 2018 14:10:44
Problema Sortare topologica Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 3.5 kb
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        InputStream inputStream = new FileInputStream("sortaret.in");
        FileWriter fileWriter = new FileWriter("sortaret.out");

        try (InputReader inputReader = new InputReader(inputStream);
             BufferedWriter bufferedWriter = new BufferedWriter(fileWriter)) {
            new Solver(inputReader, bufferedWriter).solve();
        }
    }

    static class Solver {

        private InputReader inputReader;

        private BufferedWriter bufferedWriter;

        private int N, M;

        private List<List<Integer>> graph;

        private boolean[] mark;

        private List<Integer> solution;

        public Solver(InputReader inputReader, BufferedWriter bufferedWriter) {
            this.inputReader = inputReader;
            this.bufferedWriter = bufferedWriter;
        }

        private void read() throws IOException {
            N = inputReader.nextInt();
            M = inputReader.nextInt();

            graph = new ArrayList<>(N + 1);
            mark = new boolean[N + 1];
            for (int i = 0; i <= N; i++) {
                graph.add(new LinkedList<>());
            }

            int x, y;
            for (int idx = 0; idx < M; idx++) {
                x = inputReader.nextInt();
                y = inputReader.nextInt();

                List<Integer> adjList = graph.get(y);
                adjList.add(x);
            }

            solution = new ArrayList<>(N);
        }

        private void dfs(int node) {
            mark[node] = true;
            for (int neighb : graph.get(node)) {
                if (!mark[neighb]) {
                    dfs(neighb);
                }
            }
            solution.add(node);
        }

        public void solve() throws IOException {
            read();

            Arrays.fill(mark, false);
            for (int node = 1; node <= N; node++) {
                if (!mark[node]) {
                    dfs(node);
                }
            }

            for (int idx = 0; idx < N; idx++) {
                bufferedWriter.write(solution.get(idx) + " ");
            }
            bufferedWriter.newLine();
        }
    }

    static class InputReader implements AutoCloseable {

        private static final int BUFFER_SIZE = (1 << 13);

        private BufferedInputStream bufferedInputStream;

        private byte[] bytesBuffer;

        private int bufferPos;

        public InputReader(InputStream inputStream) {
            bufferedInputStream = new BufferedInputStream(inputStream);
            bytesBuffer = new byte[BUFFER_SIZE];
            bufferPos = 0;
        }

        private void fillBuffer() throws IOException {
            bufferedInputStream.read(bytesBuffer);
            bufferPos = 0;
        }

        private byte nextByte() throws IOException {
            if (bufferPos == BUFFER_SIZE) {
                fillBuffer();
            }

            return bytesBuffer[bufferPos++];
        }

        public int nextInt() throws IOException {
            byte nextByte = nextByte();
            while (!Character.isDigit(nextByte)) {
                nextByte = nextByte();
            }

            int no = 0;
            while (Character.isDigit(nextByte)) {
                no = no * 10 + nextByte - '0';
                nextByte = nextByte();
            }

            return no;
        }

        @Override
        public void close() throws IOException {
            bufferedInputStream.close();
        }
    }
}