Cod sursa(job #2055802)

Utilizator GagosGagos Radu Vasile Gagos Data 3 noiembrie 2017 19:05:09
Problema Sortare topologica Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.15 kb
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Main {
    private static final Set<Integer> EMPTY_SET = Collections.emptySet();

    private final String inputFileName;
    private final String outputFileName;

    private Main(String inputFileName, String outputFileName) {
        this.inputFileName = inputFileName;
        this.outputFileName = outputFileName;
    }

    private void solve() throws IOException {
        Map<Integer, Set<Integer>> graph = readGraph();
        List<Integer> solution = new ArrayList<Integer>();
        Deque<Integer> dfsStack = new ArrayDeque<Integer>();
        Set<Integer> visited = new HashSet<Integer>();

        dfsStack.addLast(1);
        while (!dfsStack.isEmpty()) {
            Integer current = dfsStack.removeLast();
            Set<Integer> nodes = graph.get(current);

            if (nodes == null) {
                nodes = EMPTY_SET;
            }

            for (Integer node : nodes) {
                if (!visited.contains(node)) {
                    visited.add(node);
                    dfsStack.addLast(node);
                }
            }

            solution.add(current);
        }

        write(solution);
    }

    private Map<Integer, Set<Integer>> readGraph() throws IOException {
        try (BufferedReader reader = new BufferedReader(new FileReader(inputFileName))) {
            Map<Integer, Set<Integer>> graph = new HashMap<Integer, Set<Integer>>();
            String firstLine = reader.readLine().trim();
            int firstLineSpaceIndex = firstLine.indexOf(' ');
            int numNodes = Integer.parseInt(firstLine.substring(0, firstLineSpaceIndex));
            int numLinks = Integer.parseInt(firstLine.substring(firstLineSpaceIndex + 1));

            for (int i = 0; i < numLinks; ++i) {
                String line = reader.readLine().trim();
                int spaceIndex = firstLine.indexOf(' ');
                int from = Integer.parseInt(line.substring(0, spaceIndex));
                int to = Integer.parseInt(line.substring(spaceIndex + 1));

                if (graph.containsKey(from)) {
                    graph.get(from).add(to);
                } else {
                    graph.put(from, new HashSet<Integer>());
                }
            }

            return graph;
        }
    }

    private void write(List<Integer> solution) throws IOException {
        try (BufferedWriter writer = new BufferedWriter(new FileWriter(outputFileName))) {
            StringBuilder sb = new StringBuilder().append(solution.get(0));

            for (int i = 1; i < solution.size(); ++i) {
                sb.append(' ').append(solution.get(i));
            }

            writer.write(sb.toString());
            writer.newLine();
        }
    }

    public static void main(String[] args) throws IOException {
        new Main("sortaret.in", "sortaret.out").solve();
    }
}