Cod sursa(job #2225822)

Utilizator radustn92Radu Stancu radustn92 Data 28 iulie 2018 13:37:25
Problema Sortare topologica Scor 60
Compilator java Status done
Runda Arhiva educationala Marime 3.09 kb
import java.io.*;
import java.util.*;

public class Main {

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

        try (InputReader inputReader = new InputReader(inputStream);
            PrintWriter printWriter = new PrintWriter(outputStream)) {
            new Solver(inputReader, printWriter).solve();
        }
    }

    static class Solver {

        private InputReader inputReader;

        private PrintWriter printWriter;

        private int N, M;

        private List<List<Integer>> graph;

        private boolean[] mark;

        private List<Integer> solution;

        public Solver(InputReader inputReader, PrintWriter printWriter) {
            this.inputReader = inputReader;
            this.printWriter = printWriter;
        }

        private void read() {
            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() {
            read();

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

            for (int idx = 0; idx < N; idx++) {
                printWriter.printf("%d ", solution.get(idx));
            }
            printWriter.println();
        }
    }

    static class InputReader implements AutoCloseable {

        private BufferedReader bufferedReader;

        private StringTokenizer stringTokenizer;

        public InputReader(InputStream inputStream) {
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
            stringTokenizer = null;
        }

        private String nextToken() {
            if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return stringTokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }

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