Cod sursa(job #1239773)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 9 octombrie 2014 19:31:17
Problema Sortare topologica Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 2.53 kb
import java.io.*;
import java.util.*;
 
class FastScanner {
    private BufferedReader br;
    private StringTokenizer st;
 
    public FastScanner(InputStream stream) {
        br = new BufferedReader(new InputStreamReader(stream));
    }
 
    private String next() {
        while (st == null || !st.hasMoreTokens()) {
            String line = null;
            try {
                line = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (line == null)
                return null;
            st = new StringTokenizer(line);
        }
        return st.nextToken();
    }
 
    public int nextInt() {
        return Integer.parseInt(next());
    }
 
    public long nextLong() {
        return Long.parseLong(next());
    }
 
    public double nextDouble() {
        return Double.parseDouble(next());
    }
}
 
public class Main {
    private static List<List<Integer>> G;
    private static int V;
     
    private static void DFS(final int x, final boolean[] visited, final List<Integer> topologicalSort) {
        visited[x] = true;
        for (int y: G.get(x))
            if (!visited[y])
                DFS(y, visited, topologicalSort);
        topologicalSort.add(x);
    }
     
    private static void addEdge(final int from, final int to) {
        G.get(from).add(to);
    }
    
    private static List<Integer> getTopologicalSort() {
    	boolean[] visited = new boolean[V];
    	List<Integer> topologicalSort = new ArrayList<Integer>();
    	for (int x = 0; x < V; ++x)
    		if (!visited[x])
    			DFS(x, visited, topologicalSort);
    	Collections.reverse(topologicalSort);
    	return topologicalSort;
    }
     
    public static void main(String[] args) throws IOException {
        FastScanner reader = new FastScanner(new FileInputStream("sortaret.in"));
        V = reader.nextInt();
        G = new ArrayList<List<Integer>>(V);
        for (int x = 0; x < V; ++x)
            G.add(new ArrayList<Integer>());
        int edgeCount = reader.nextInt();
        for (; edgeCount > 0; --edgeCount) {
            int x = reader.nextInt() - 1;
            int y = reader.nextInt() - 1;
            addEdge(x, y);
        }
        
        List<Integer> topologicalSort = getTopologicalSort();
         
        PrintWriter writer = new PrintWriter("sortaret.out");
        for (int x: topologicalSort)
        	writer.write((x + 1) + " ");
        writer.write("\n");
        writer.close();
    }
}