Cod sursa(job #1854383)

Utilizator vladradu97150Vlad Radu vladradu97150 Data 22 ianuarie 2017 17:49:19
Problema Sortare topologica Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.35 kb
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

class Main {
	static int N;
	static byte color[];
	static List<List<Integer>> adjList = new LinkedList<>();
	static Stack<Integer> topoSort = new Stack<>(); 
	
	static void dfs(int start) {
		color[start] = 1;
		for(int neighbor : adjList.get(start)) {
			if (color[neighbor] == 0) {
				dfs(neighbor);
			}
		}
		color[start] = 2;
		topoSort.add(start);
	}

	public static void main(String[] args) throws FileNotFoundException, IOException {
		try(FileReader freader = new FileReader("sortaret.in");
				Scanner scanner = new Scanner(freader);
				FileWriter fwriter = new FileWriter("sortaret.out");
				BufferedWriter bwriter = new BufferedWriter(fwriter)) {
			N = scanner.nextInt();
			int M = scanner.nextInt();
			color = new byte[N+1];
			for(int i=0;i<N+1;i++) {
				adjList.add(new LinkedList<>());
			}
			for(int i=0;i<M;i++) {
				adjList.get(scanner.nextInt()).add(scanner.nextInt());
			}
			
			for(int i=1;i<=N;i++) {
				if(color[i] == 0) {
					dfs(i);
				}
			}
			
			while(!topoSort.isEmpty()) {
				bwriter.write(topoSort.pop() + " ");
			}
		}

	}

}