Cod sursa(job #1792024)

Utilizator greenadexIulia Harasim greenadex Data 29 octombrie 2016 22:57:18
Problema Sortare topologica Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 2.5 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 {
        Scanner reader = new Scanner(new FileReader("sortaret.in"));
        BufferedWriter writer = new BufferedWriter(new FileWriter("sortaret.out"));

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

        reader.close();
        writer.close();
    }

    private static Graph readInput(Scanner 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(List<Integer> results, Writer writer) throws IOException {
        for (Integer vertex : results) {
            writer.write(vertex + " ");
        }
    }
}