Cod sursa(job #1705387)

Utilizator deeagrtAndGrt deeagrt Data 20 mai 2016 14:59:03
Problema Sortare topologica Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 1.55 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.io.PrintStream;
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();
		 
	}
}