Cod sursa(job #1363300)

Utilizator vlad.maneaVlad Manea vlad.manea Data 26 februarie 2015 21:08:08
Problema Sortare topologica Scor 70
Compilator java Status done
Runda Arhiva educationala Marime 2.08 kb
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

class Graph {
	private List<List<Integer>> adj;
	private Map<Integer, Integer> map;
	private Map<Integer, Integer> ord;
	private int value;

	Graph(List<List<Integer>> adj) {
		this.adj = adj;
	}
	
	List<Integer> topoSort() {
		int N = adj.size();
		map = new HashMap<Integer, Integer>(N);
		ord = new HashMap<Integer, Integer>(N);
		value = 0;
		
		for (int node = 0; node < N; ++node) {
			topoSort(node);
		}
		
		List<Integer> values = new ArrayList<Integer>(N);
		
		for (int node = 0; node < N; ++node) {
			values.add(1 + ord.get(node));
		}
		
		return values;
	}
	
	private void topoSort(int node) {
		if (map.containsKey(node)) {
			return;
		}
		
		List<Integer> siblings = adj.get(node);
		
		for (int sibling : siblings) {
			topoSort(sibling);
		}
		
		ord.put(value, node);
		map.put(node, value++);
	}
}

public class Main {
	public static void main(String[] args) throws IOException {
		InputStream inputStream = new FileInputStream("sortaret.in");
		Scanner scanner = new Scanner(inputStream);

		OutputStream outputStream = new FileOutputStream("sortaret.out");
		PrintWriter writer = new PrintWriter(outputStream);
		
		int N = scanner.nextInt();
		int M = scanner.nextInt();
		
		List<List<Integer>> adj = new ArrayList<List<Integer>>(N);
		
		for (int i = 0; i < N; ++i) {
			adj.add(new ArrayList<Integer>());
		}
		
		while (M-- > 0) {
			int x = scanner.nextInt() - 1;
			int y = scanner.nextInt() - 1;
			adj.get(y).add(x);
		}
		
		Graph graph = new Graph(adj);
		List<Integer> topoSort = graph.topoSort();
		
		for (int node : topoSort) {
			writer.print(node);
			writer.print(" ");
		}
		
		writer.flush();

		inputStream.close();
		scanner.close();

		outputStream.close();
		writer.close();
	}
}