Cod sursa(job #2147920)

Utilizator btkroSilviu Troscot btkro Data 1 martie 2018 11:38:16
Problema Sortare topologica Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.61 kb
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.FileNotFoundException;


public class Main {
    public static void main(String[] args) throws FileNotFoundException, IOException {
        InputStream inputStream = new FileInputStream(new File("sortaret.in"));
        OutputStream outputStream = new FileOutputStream(new File("sortaret.out"));
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task{
        static final int INF = (int) 1.01e9;

        public void solve(InputReader in, PrintWriter out){
            int numberOfNodes = in.nextInt();
            int numberOfEdges = in.nextInt();
            // construct the graph
            List<List<Integer>> graph = new ArrayList<>(numberOfNodes + 2);
            for(int i = 0; i <= numberOfNodes; i++) {
                graph.add(new ArrayList<Integer>());
            }
            for (int i = 0; i < numberOfEdges; i++) {
            	int source = in.nextInt();
            	int destination = in.nextInt();
            	if (graph.get(source) != null) {
            		List<Integer> adjList = graph.get(source);
            		adjList.add(destination);
            		graph.add(source, adjList);
            	}
            	else {
            		List<Integer> adjList = new ArrayList<>();
            		adjList.add(destination);
            		graph.add(source, adjList);
            	}
            }

            List<Integer> result = topologicalSort(graph, numberOfNodes);
            for (int i = result.size() - 1; i>= 0; i--) {
            	out.write(result.get(i).toString());
            	out.write(" ");
            }

        }

        public void dfs(int startNode, List<List<Integer>> graph, 
        				 Set<Integer> visited, List<Integer> result) {

        	if (graph.get(startNode) == null) {
				visited.add(startNode);
				result.add(startNode);
        		return;
        	}

        	visited.add(startNode);
        	for (int neighbour : graph.get(startNode)) {
        		if (!visited.contains(neighbour)) {
        			dfs(neighbour, graph, visited, result);	
        		}
        	}	
        	result.add(startNode);
        }

        public List<Integer> topologicalSort(List<List<Integer>> graph,
        									 int noOfNodes) {
        	List<Integer> result = new ArrayList<>();
        	Set<Integer> visited = new HashSet<>();
        	for (int node = 1; node <= noOfNodes; node++) {
        		if (!visited.contains(node)) {
        			dfs(node, graph, visited, result);
        		}
        	}

        	return result;
        }
    
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}