Cod sursa(job #1749142)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 27 august 2016 22:06:08
Problema Sortare topologica Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 4.27 kb
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner(new FileInputStream("sortaret.in"));

        int N = in.nextInt();
        int M = in.nextInt();

        Graph G = new Graph(N);

        for (int i = 0; i < M; i++) {
            int u = in.nextInt();
            int v = in.nextInt();

            G.addEdge(u, v);
        }

        int[] topSort = TopologicalSorting.topologicalSorting(G);

        PrintWriter out = new PrintWriter(new FileOutputStream("sortaret.out"));

        for (int i = 0; i < N; i++) {
            out.printf("%d ", topSort[i]);
        }

        out.println();
        out.close();
    }

    static class TopologicalSorting {
        private static void dfs(int node, final Graph G, final boolean[] visited, final ArrayList<Integer> list){
            visited[node] = true;
            list.add(node);

            for (int p = G.getHead(node); p != Graph.NIL; p = G.getNext(p)) {
                int son = G.getNeighbour(p);

                if (!visited[son])
                    dfs(son, G, visited, list);
            }
        }

        static int[] topologicalSorting(final Graph graph){
            final int N = graph.getN();
            boolean[] visited = new boolean[N + 1];
            ArrayList<Integer> list = new ArrayList<>();

            for (int i = 1; i <= N; i++) {
                if (!visited[i])
                    dfs(i, graph, visited, list);
            }

            int[] topSort = new int[N];

            for (int i = 0; i < list.size(); i++) {
                topSort[i] = list.get(i);
            }

            return topSort;
        }
    }

    static class Graph{
        private static class Edge{
            int node;
            int next;

            Edge(int node, int next){
                this.node = node;
                this.next = next;
            }
        }

        final static int NIL = -1;
        private int[] head;
        private int[] degree;
        private ArrayList<Edge> graph;

        private int N;
        private int counter;

        Graph(int N){
            initialize(N);
        }

        public int getN() {
            return N;
        }

        private void initialize(final int N){
            head = new int[N];
            degree = new int[N];
            graph = new ArrayList<>();

            this.N = N;
            this.counter = 0;

            Arrays.fill(head, NIL);
            Arrays.fill(degree, 0);
        }

        void addEdge(int x, int y){
            if (!(1 <= x && x <= N)) throw new AssertionError();
            x--; y--;
            graph.add(new Edge(y, head[x]));
            head[x] = counter++;
            degree[x]++;
        }

        int getHead(int node){
            if (!(1 <= node && node <= N)) throw new AssertionError();
            node--;
            return head[node];
        }

        int getNext(int p){
            if (!(0 <= p && p < counter)) throw new AssertionError();
            return graph.get(p).next;
        }

        int getNeighbour(int p){
            if (!(0 <= p && p < counter)) throw new AssertionError();
            return graph.get(p).node + 1;
        }

        boolean isEmpty(int node){
            if (!(1 <= node && node <= N)) throw new AssertionError();
            node--;
            return head[node] == NIL;
        }

        int size(int node){
            assert 1 <= node && node <= N;
            node--;
            return degree[node];
        }

        Graph transpose(){
            Graph GT = new Graph(N);

            for (int i = 1; i <= N; i++) {
                for (int son : getNeighbours(i))
                    GT.addEdge(son, i);
            }

            return GT;
        }

        List<Integer> getNeighbours(int node){
            if (!(1 <= node && node <= N)) throw new AssertionError();

            List<Integer> list = new ArrayList<>();

            for (int p = head[node - 1]; p != NIL; p = graph.get(p).next) {
                list.add(graph.get(p).node + 1);
            }

            return list;
        }
    }

}