Cod sursa(job #1744335)

Utilizator AplayLazar Laurentiu Aplay Data 19 august 2016 17:03:32
Problema Sortare topologica Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 1.58 kb
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Main {

	private static boolean[] visited;
	private static int N, M;
	private static List<Integer>[] graph;
	private static Stack<Integer> stack = new Stack<>();

	private static int[] parseLine(String line) {
		int it = 0;
		int[] result = new int[2];

		for (String element : line.split(" ")) {
			result[it++] = Integer.parseInt(element);
		}

		return result;
	}

	private static void dfs(int currNode) {
		visited[currNode] = true;
		
		for (int neighbor : graph[currNode]) {
			if (!visited[neighbor]) {
				dfs(neighbor);
			}
		}
		
		stack.push(currNode);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new FileReader("sortaret.in"));
		BufferedWriter writer = new BufferedWriter(new FileWriter("sortaret.out"));

		int[] tmp;

		tmp = parseLine(reader.readLine());
		N = tmp[0];
		M = tmp[1];

		graph = new List[N + 1];
		visited = new boolean[N + 1];

		for (int it = 1; it <= N; ++it) {
			graph[it] = new ArrayList<>();
		}

		for (int it = 0; it < M; ++it) {
			tmp = parseLine(reader.readLine());
			graph[tmp[0]].add(tmp[1]);
		}

		for (int it = 1; it <= N; ++it) {
			if (!visited[it]) {
				dfs(it);
			}
		}
		
		while (!stack.isEmpty()) {
			writer.write(stack.pop() + " ");
		}
		
		reader.close();
		writer.close();
	}

}