Pagini recente » Cod sursa (job #1975397) | Cod sursa (job #830356) | Cod sursa (job #17349) | Cod sursa (job #289762) | Cod sursa (job #2198959)
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;
}
}