Cod sursa(job #1416239)

Utilizator ibicecIT Zilla ibicec Data 7 aprilie 2015 17:46:39
Problema Sortare topologica Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.42 kb
import java.io.*;
import java.util.*;

public class TopologicalSort {

    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner( new FileInputStream("sortaret.in"));
        int n = sc.nextInt(), m = sc.nextInt();

        Graph graph = new Graph(n);
        for (int i=0; i<n; i++) {
            graph.addVertex(i);
        }
        for ( int i=0; i<m; i++) {
            int src = sc.nextInt();
            int dst = sc.nextInt();
            graph.addEdge(src-1, dst-1);
        }
        sc.close();

        PrintWriter pw = new PrintWriter("sortaret.out");
        for ( int i=0; i<n; i++ ) {
            Vertex noSuccVertex = graph.getNoSuccesorVertex();
            pw.print(noSuccVertex.getId()+1);
            pw.print(' ');
            graph.removeVertex(noSuccVertex.getId());
        }
        pw.close();
    }
}

class Vertex {
    int id;

    Vertex(int id) {
        this.id = id;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }
}

class Graph {
    Vertex[] vertices;
    Object[] adjList;
    int numVertices;

    Graph(int maxVertices) {
        vertices = new Vertex[maxVertices];
        adjList = new Object[maxVertices];
    }

    public void addVertex(int id) {
        vertices[numVertices] = new Vertex(id);
        adjList[numVertices] = new LinkedList<Integer>();
        ++numVertices;
    }

    public void addEdge(int sourceID, int destID) {
        ((List<Integer>)adjList[sourceID]).add(destID);
    }

    public Vertex getNoSuccesorVertex() {
        boolean[] hasSuccesors = new boolean[numVertices];
        for (int i=0; i<numVertices; i++) {
            if ( adjList[i] != null ) {
                for (Integer o : (List<Integer>) adjList[i]) {
                    hasSuccesors[o] = true;
                }
            }
        }
        for ( int i=0; i<numVertices; i++ ) {
            if ( !hasSuccesors[i] && vertices[i] != null ) {
                return vertices[i];
            }
        }
        return null;
    }

    public void removeVertex(int id) {
        vertices[id] = null;
        adjList[id] = null;
        for (int i=0; i<numVertices; i++) {
            if ( adjList[i] != null ) {
                ((LinkedList<Integer>)adjList[i]).removeLastOccurrence(id);
            }
        }
    }

}