Cod sursa(job #2564963)

Utilizator AplayLazar Laurentiu Aplay Data 2 martie 2020 11:20:00
Problema Sortare topologica Scor 20
Compilator java Status done
Runda Arhiva educationala Marime 1.69 kb
import java.io.File;
import java.util.Scanner;
import java.io.IOException;
import java.util.List;
import java.util.ArrayList;
import java.io.BufferedWriter;
import java.io.FileWriter;

public final class Main {

    public final static void main(final String[] args) throws IOException {
        final Scanner in = new Scanner(new File("sortaret.in"));

        final int N = in.nextInt();
        final int M = in.nextInt();

        final int[] inDegree = new int[1 + N];
        final List<Integer>[] adj = new List[1 + N];
        int from, to;
        for (int it = 0; it < M; ++it) {
            from = in.nextInt();
            to = in.nextInt();
            if (null == adj[from]) {
                adj[from] = new ArrayList<>();
            }
            adj[from].add(to);
            ++inDegree[to];
        }

        in.close();

        final BufferedWriter out = new BufferedWriter(new FileWriter("sortaret.out"));

        final List<Integer> canBeNext = new ArrayList<>();
        for (int it = 1; it <= N; ++it) {
            if (0 == inDegree[it]) {
                canBeNext.add(it);
            }
        }
        while (!canBeNext.isEmpty()) {
            final int next = canBeNext.get(canBeNext.size() - 1);
            canBeNext.remove(canBeNext.size() - 1);
            out.write(next + " ");
            if (null != adj[next]) {
                for (int it = 0; it < adj[next].size(); ++it) {
                    --inDegree[adj[next].get(it)];
                    if (0 == inDegree[adj[next].get(it)]) {
                        canBeNext.add(adj[next].get(it));
                    }
                }
            }
        }

        out.write("\n");
        out.flush();
        out.close();
    }

}