Cod sursa(job #1749046)

Utilizator raduta_vladVlad Raduta raduta_vlad Data 27 august 2016 19:07:58
Problema A+B Scor 0
Compilator java Status done
Runda teme_upb Marime 1.16 kb
import java.util.*;
import java.io.File;
import java.io.FileNotFoundException;

public class SortareTopologica {
	
	
	public static void main(String[] args) throws FileNotFoundException{
		// TODO Auto-generated method stub
		Scanner in = new Scanner(new File("sortaret.in"));
			
			int n = in.nextInt();
			
			Graph graph = new Graph(n);
			
			int m = in.nextInt();
			while (m>0){
				m--;
				int i=in.nextInt();
				int j=in.nextInt();
				graph.addEdge(i, j);
			}		
		
		List<Integer> res = SortTp(graph);
		
		Iterator<Integer> it = res.iterator();
		
		while (it.hasNext()){
			System.out.print(it.next() + " ");
		}
		
	}
	
	public static List<Integer> SortTp(Graph graph){
		int n = graph.getTotalNUmOfNodes();
		int[] visited = new int[n];
		List<Integer> res = new ArrayList<Integer>();

		for (int i = 0; i < n; i++)
			if(visited[i] == 0)
				dfs(graph, visited, res, i);
				
		return res;
	}
	
	static void dfs(Graph graph, int[] visited, List<Integer> res, int u){

		visited[u] = 1;
		
		for (int v : graph.getNeighboursOf(u))
			if (visited[v] == 0)
				dfs(graph, visited, res, v);
		res.add(u);
		
	}
	
}