Cod sursa(job #2147923)

Utilizator btkroSilviu Troscot btkro Data 1 martie 2018 11:43:37
Problema Sortare topologica Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 3.71 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
            Map<Integer, List<Integer>> graph = new HashMap<>();
            for (int i = 0; i < numberOfEdges; i++) {
                int source = in.nextInt();
                int destination = in.nextInt();
                if (graph.containsKey(source)) {
                    List<Integer> adjList = graph.get(source);
                    adjList.add(destination);
                    graph.put(source, adjList);
                }
                else {
                    List<Integer> adjList = new ArrayList<>();
                    adjList.add(destination);
                    graph.put(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, Map<Integer, List<Integer>> graph, 
                         Set<Integer> visited, List<Integer> result) {
 
            if (!graph.containsKey(startNode)) {
                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(Map<Integer, 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());
        }
 
    }
}