Pagini recente » Cod sursa (job #2998937) | Cod sursa (job #323646) | Cod sursa (job #1972908) | Cod sursa (job #786552) | Cod sursa (job #1869921)
import java.io.*;
import java.util.*;
class topsort {
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(new FileReader("sortaret.in"));
int n = in.nextInt(), m = in.nextInt();
Graph graph = new Graph(n);
for (int i = 0; i < m; ++i) {
int x = in.nextInt(), y = in.nextInt();
graph.addEdge(x - 1, y - 1);
}
in.close();
List<Integer> sorted = TopologicalSort.topSort(graph);
FileWriter out = new FileWriter("sortaret.out");
for (int i : sorted) {
out.write((i + 1) + " ");
}
out.close();
}
}
class TopologicalSort {
public static List<Integer> topSort(Graph g) {
Queue<Integer> queue = new LinkedList<Integer>();
int n = g.numberOfNodes();
for (int i = 0; i < n; ++i) {
if (g.getNode(i).getIndegree() == 0) {
queue.add(i);
}
}
List<Integer> sorted = new ArrayList<Integer>();
while (!queue.isEmpty()) {
int node = queue.poll();
sorted.add(node);
for (int neighbour : g.getNode(node).getEdges()) {
g.getNode(neighbour).decreaseIndegree();
if (g.getNode(neighbour).getIndegree() == 0) {
queue.add(neighbour);
}
}
}
return sorted;
}
}
class Graph {
private List<Node> nodes;
public Graph(int n) {
nodes = new ArrayList<Node>(n);
for (int i = 0; i < n; ++i) {
nodes.add(new Node());
}
}
public void addEdge(int x, int y) {
nodes.get(x).addEdge(y);
nodes.get(y).increaseIndegree();
}
public int numberOfNodes() {
return nodes.size();
}
public Node getNode(int i) {
return nodes.get(i);
}
protected static class Node {
private int indegree;
private List<Integer> edges;
public Node() {
indegree = 0;
edges = new ArrayList<Integer>();
}
public void addEdge(int neighbour) {
edges.add(neighbour);
}
public List<Integer> getEdges() {
return Collections.unmodifiableList(edges);
}
public int getIndegree() {
return indegree;
}
public void increaseIndegree() {
++indegree;
}
public void decreaseIndegree() {
--indegree;
}
}
}