Cod sursa(job #1869919)

Utilizator preda.andreiPreda Andrei preda.andrei Data 6 februarie 2017 11:29:25
Problema Sortare topologica Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.58 kb
import java.io.*;
import java.util.*;

public class topsort {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(new FileReader("sortaret.in"));
        int n = in.nextInt(), m = in.nextInt();
        Graph graph = new Graph(n);

        for (int i = 0; i < m; ++i) {
           int x = in.nextInt(), y = in.nextInt();
           graph.addEdge(x - 1, y - 1);
        }
        in.close();

        List<Integer> sorted = TopologicalSort.topSort(graph);
        FileWriter out = new FileWriter("sortaret.out");
        for (int i : sorted) {
           out.write((i + 1) +  " ");
        }
        out.close();
    }
}

class TopologicalSort {
    public static List<Integer> topSort(Graph g) {
        Queue<Integer> queue = new LinkedList<Integer>();
        int n = g.numberOfNodes();

        for (int i = 0; i < n; ++i) {
            if (g.getNode(i).getIndegree() == 0) {
                queue.add(i);
            }
        }

        List<Integer> sorted = new ArrayList<Integer>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            sorted.add(node);

            for (int neighbour : g.getNode(node).getEdges()) {
                g.getNode(neighbour).decreaseIndegree();
                if (g.getNode(neighbour).getIndegree() == 0) {
                    queue.add(neighbour);
                }
            }
        }
        return sorted;
    }
}

class Graph {

    private List<Node> nodes;

    public Graph(int n) {
        nodes = new ArrayList<Node>(n);
        for (int i = 0; i < n; ++i) {
            nodes.add(new Node());
        }
    }

    public void addEdge(int x, int y) {
        nodes.get(x).addEdge(y);
        nodes.get(y).increaseIndegree();
    }

    public int numberOfNodes() {
        return nodes.size();
    }

    public Node getNode(int i) {
        return nodes.get(i);
    }

    protected static class Node {
        private int indegree;
        private List<Integer> edges;

        public Node() {
            indegree = 0;
            edges = new ArrayList<Integer>();
        }

        public void addEdge(int neighbour) {
            edges.add(neighbour);
        }

        public List<Integer> getEdges() {
            return Collections.unmodifiableList(edges);
        }

        public int getIndegree() {
            return indegree;
        }

        public void increaseIndegree() {
            ++indegree;
        }

        public void decreaseIndegree() {
            --indegree;
        }
    }
}