Cod sursa(job #1792042)

Utilizator greenadexIulia Harasim greenadex Data 29 octombrie 2016 23:11:18
Problema Sortare topologica Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.17 kb
package topo_sort;

import java.io.*;
import java.util.*;

/**
 * Created on 29.10.2016.
 */

class Node {
    private int value;
    private List<Node> adjacent;

    Node(int value) {
        this.value = value;
        adjacent = new ArrayList<>();
    }

    List<Node> getAdjacent() {
        return adjacent;
    }

    void addAdjacent(Node node) {
        adjacent.add(node);
    }

    int getValue() {
        return value;
    }
}

class Graph {
    private List<Node> vertices;

    Graph(int size) {
        vertices = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            vertices.add(new Node(i + 1));
        }
    }

    void dfs(Node current, Set<Node> visited, Stack<Node> stack) {
        visited.add(current);
        for (Node adj : current.getAdjacent()) {
            if (!visited.contains(adj)) {
                dfs(adj, visited, stack);
            }
        }
        stack.add(current);
    }

    void addEdge(int x, int y) {
        vertices.get(x - 1).addAdjacent(vertices.get(y - 1));
    }

    List<Node> getVertices() {
        return vertices;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        InputReader reader = new InputReader("sortaret.in");
        BufferedWriter writer = new BufferedWriter(new FileWriter("sortaret.out"));

        Graph graph = readInput(reader);
        List<Integer> results = solveTask(graph);
        writeResults(writer, results);
    }

    private static Graph readInput(InputReader reader) {
        int noOfVertices = reader.nextInt(),
                noOfEdges = reader.nextInt();

        Graph graph = new Graph(noOfVertices);
        for (int i = 0; i < noOfEdges; i++) {
            graph.addEdge(reader.nextInt(), reader.nextInt());
        }

        return graph;
    }

    private static List<Integer> solveTask(Graph graph) {
        Set<Node> visited = new HashSet<>();
        Stack<Node> stack = new Stack<>();
        for (Node node : graph.getVertices()) {
            if (!visited.contains(node)) {
                graph.dfs(node, visited, stack);
            }
        }

        List<Integer> results = new ArrayList<>();
        while (!stack.isEmpty()) {
            results.add(stack.pop().getValue());
        }
        return results;
    }

    private static void writeResults(Writer writer, List<Integer> results) throws IOException {
        for (Integer vertex : results) {
            writer.write(vertex + " ");
        }
    }

    private static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(String fileName) throws FileNotFoundException {
            reader = new BufferedReader(new FileReader(fileName), 32768);
            tokenizer = null;
        }

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

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