Cod sursa(job #2198959)

Utilizator ibicecIT Zilla ibicec Data 25 aprilie 2018 22:41:36
Problema Sortare topologica Scor 50
Compilator java Status done
Runda Arhiva educationala Marime 2.55 kb
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws FileNotFoundException {
        Scanner scanner = new Scanner(new FileReader("sortaret.in"));
        int n = scanner.nextInt(), m = scanner.nextInt();
        DirectedGraph graph = new DirectedGraph(n);
        for (int i=0; i<m; i++) {
            graph.addEdge(scanner.nextInt()-1, scanner.nextInt()-1);
        }
        scanner.close();

        PrintWriter printWriter = new PrintWriter("sortaret.out");
        List<Integer> sortedVertices = graph.topologicalSort();
        for (Integer vertex: sortedVertices) {
            printWriter.printf("%d ", vertex+1);
        }
        printWriter.close();
    }
}

class DirectedGraph {

    private List<Integer>[] adjList;
    private int[] inDegrees;

    @SuppressWarnings("unchecked")
    DirectedGraph(int vertices) {
        if (vertices < 1) {
            throw new IllegalArgumentException("There should be at least one node in the graph");
        }
        this.adjList = new List[vertices];
        this.inDegrees = new int[vertices];
    }

    void addEdge(int s, int d) {
        if (s < 0 || s >= adjList.length) {
            throw new IllegalArgumentException(String.format("Invalid source node: %d, vertices in graph: %d", s, adjList.length));
        }
        if (d < 0 || d >= adjList.length) {
            throw new IllegalArgumentException(String.format("Invalid destination node: %d, vertices in graph: %d", d, adjList.length));
        }
        if (adjList[s] == null) {
            adjList[s] = new LinkedList<>();
        }
        adjList[s].add(d);
        inDegrees[d]++;
    }

    List<Integer> topologicalSort() {
        List<Integer> result = new LinkedList<>();

        Queue<Integer> queue = new LinkedList<>();
        int[] inDegrees = this.inDegrees.clone();
        for (int i=0; i<inDegrees.length; i++) {
            if (inDegrees[i] == 0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            Integer vertex = queue.poll();
            result.add(vertex);
            if (adjList[vertex] != null) {
                for (Integer adjVertex : adjList[vertex]) {
                    inDegrees[adjVertex]--;
                    if (inDegrees[adjVertex] == 0) {
                        queue.add(adjVertex);
                    }
                }
            }
        }

        return result;
    }


}