Cod sursa(job #1705553)

Utilizator greenroFlorin Calota greenro Data 20 mai 2016 19:27:12
Problema Sortare topologica Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 1.74 kb
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.OutputStream;
import java.util.ArrayList;

public class Main {

    static ArrayList<Integer>[] adj;
    static int[] visited;
    static ArrayList<Integer> sol;

    public static void dfs(int n) {
        visited[n] = 1;
        for (Integer x : adj[n]) {
            if (visited[x] != 1) {
                dfs(x);
            }
        }
        sol.add(n);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new FileReader("sortaret.in"));
        //PrintStream out = new PrintStream();
        OutputStream out = new BufferedOutputStream(new FileOutputStream("sortaret.out"));
        String tmp[] = bf.readLine().split(" ");
        int n = Integer.parseInt(tmp[0]);
        int m = Integer.parseInt(tmp[1]);

        adj = new ArrayList[n + 1];
        sol = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < m; i++) {
            tmp = bf.readLine().split(" ");
            int x = Integer.parseInt(tmp[0]);
            int y = Integer.parseInt(tmp[1]);
            adj[x].add(y);
        }

        visited = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            if (visited[i] != 1) {
                dfs(i);
            }
        }

        for (int i = sol.size() - 1; i >= 0; i--) {
            out.write((sol.get(i) + " ").getBytes());
        }
        out.write(("\n").getBytes());
        out.flush();
        out.close();
        bf.close();

    }
}