Pagini recente » Cod sursa (job #1137597) | Cod sursa (job #897888) | Cod sursa (job #462656) | Cod sursa (job #1681367) | Cod sursa (job #1416239)
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);
}
}
}
}