Cod sursa(job #1703554)

Utilizator cristian.diaconuDiaconu Cristian cristian.diaconu Data 17 mai 2016 09:22:48
Problema Sortare topologica Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 3.44 kb
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.logging.Level;
import java.util.logging.Logger;

class MyScanner {
    BufferedReader br;
    StringTokenizer st;
 
    public MyScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    
    public MyScanner(String name) throws FileNotFoundException {
    	InputStream input = new FileInputStream(name);
        br = new BufferedReader(new InputStreamReader(input));
    }
 
    public String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        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 String nextLine(){
        String str = "";
        try {
            str = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

class Graph {
	
	int nodes;
	ArrayList<ArrayList<Integer>> adjList;
	
	public Graph(int N) {
		nodes = N;
		adjList = new ArrayList<ArrayList<Integer>>();
		for(int i = 0; i <= nodes; i++) {
			adjList.add(i, new ArrayList<Integer>());
		}
	}
	
	public void addEdge(int src, int dest) {
		adjList.get(src).add(dest);
	}
	
	public void readData(MyScanner sc, int nrEdges) {
		
		int src, dest;
		
		for(int i = 0; i < nrEdges; i++) {
			src = sc.nextInt();
			dest = sc.nextInt();
			
			this.addEdge(src,  dest);
		}
		
	}
	
}

class Main {
	
	public static int M;
	public static int N;
	public static int[][] finTime;
	public static boolean[] grey;
	public static boolean[] black;
	public static int time;
	public static int counter;
	
	public static void topologicalSort(Graph g) {
		for(int i = 1; i <= N; i++) {
			if(!black[i]) {
				visit(g, i);
			}
		}
	}
	
	public static void visit(Graph g, int root) {
		
		time++;
		grey[root] = true;
		
		for(int i = 0; i < g.adjList.get(root).size(); i++) {
			int v = g.adjList.get(root).get(i);
			if((!grey[v]) && (!black[v])) {
				visit(g, v);
			}
		}
		
		grey[root] = false;
		black[root] = true;
		finTime[0][counter] = root;
		finTime[1][counter] = time++;
		counter++;
		
	}
	
	public static void main(String[] args) throws FileNotFoundException {
		MyScanner sc = new MyScanner("sortaret.in");
		N = sc.nextInt();
		M = sc.nextInt();
		finTime = new int[2][N];
		grey = new boolean[N + 1];
		black = new boolean[N + 1];
		Graph g = new Graph(N);
		g.readData(sc, M);
		time = 0;
		counter = 0;
		topologicalSort(g);
		try {
			PrintWriter out = new PrintWriter(new File("sortaret.out"));
			for(int i = N - 1; i >= 1; i--) {
				out.print(finTime[0][i] + " ");
			}
			out.println(finTime[0][0]);
			out.close();
		} catch (IOException ex) {
            Logger.getLogger(Main.class.getName()).log(Level.SEVERE, null, ex);
        }
		
	}
	
}