Cod sursa(job #1705831)

Utilizator iliaIulia Nicula ilia Data 20 mai 2016 23:58:33
Problema Sortare topologica Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 1.35 kb
import java.util.*;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;

class Main {
	static List<List<Integer>> graph;
	static boolean visited[];
	static int indegree[];
	static int N;
	
	static void topSort() throws FileNotFoundException {
		List<Integer> res = new ArrayList<>();
		Stack<Integer> s = new Stack<>();
		for (int u = 1; u <= N; u++) 
			if(indegree[u] == 0) {
				s.push(u);
			}
		
		int u;
		while (!s.isEmpty()) {
			u = s.pop();
			res.add(u);
			List<Integer> successors = graph.get(u);
			for (Integer v : successors) {
				indegree[v]--;
				if (indegree[v] == 0) {
					s.push(v);
				}
			}
		}
		PrintWriter output = new PrintWriter("sortaret.out");
		for(Integer i : res)
			output.print(i + " ");
		output.close();
	}
	
	
	static void init_graph(int n) {
		graph = new ArrayList<>();
		for (int i = 0; i <= n; i++)
			graph.add(new ArrayList<Integer>());
	}
	
	public static void main(String[] args) throws IOException {
		Scanner input = new Scanner(new FileReader("sortaret.in"));
		N = input.nextInt();
		int M = input.nextInt();
		indegree = new int[N + 1];
		init_graph(N);
		int node1, node2;
		for (int i = 0; i < M; i++) {
			node1 = input.nextInt();
			node2 = input.nextInt();
			graph.get(node1).add(node2);
			indegree[node2]++;
		}
		topSort();
		input.close();
	}
}