Cod sursa(job #2225345)

Utilizator amimunAmelia Munteanu amimun Data 26 iulie 2018 18:25:35
Problema Sortare topologica Scor 10
Compilator java Status done
Runda Arhiva educationala Marime 1.96 kb
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        String line;
        StringTokenizer st;
        int N, M, i, n1, n2, x;
        int[] exteriorDegree;
        int[][] a;
        LinkedList<Integer> list = new LinkedList<>();
        try {
            BufferedReader reader = new BufferedReader(new FileReader("sortaret.in"));
            PrintWriter writer = new PrintWriter("sortaret.out");
            line = reader.readLine();
            st = new StringTokenizer(line, " ");
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            exteriorDegree = new int[N+1];
            a = new int[N+1][N+1];
            for (i = 1; i <= M; i++) {
                line = reader.readLine();
                st = new StringTokenizer(line, " ");
                n1 = Integer.parseInt(st.nextToken());
                n2 = Integer.parseInt(st.nextToken());
                a[n1][n2] = 1;
                exteriorDegree[n1]++;
            }
            for (i = 1; i <= N; i++) {
                if (exteriorDegree[i] == 0) {
                    list.add(i);
                }
            }
            for (i = 0; i < N; i++) {
                x = list.get(i);
                for (int j = 1; j <= N; j++) {
                    if (a[j][x] == 1) {
                        exteriorDegree[j]--;
                        if(exteriorDegree[j] == 0) {
                            list.add(j);
                        }
                    }
                }
            }
            for (i = 1; i <= N; i++) {
                writer.write(list.pollLast() + ((i == N) ? "" : " "));
            }
            reader.close();
            writer.close();
        } catch(Exception e) {
            e.printStackTrace();
        }
    }
}