Pagini recente » Cod sursa (job #706368) | Cod sursa (job #2708299) | Cod sursa (job #1059390) | Istoria paginii runda/aaaaa/clasament | Cod sursa (job #1869959)
import java.io.*;
import java.util.*;
class Main {
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) {
int n = g.numberOfNodes();
List<Integer> sorted = new ArrayList<Integer>(n);
for (int i = 0; i < n; ++i) {
if (!g.getNode(i).wasVisited()) {
Dfs(g, i, sorted);
}
}
Collections.reverse(sorted);
return sorted;
}
private static void Dfs(Graph g, int node, List<Integer> sorted) {
g.getNode(node).setVisited(true);
for (int neighbour : g.getNode(node).getEdges()) {
if (!g.getNode(neighbour).wasVisited()) {
Dfs(g, neighbour, sorted);
}
}
sorted.add(node);
}
}
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);
}
public int numberOfNodes() {
return nodes.size();
}
public Node getNode(int i) {
return nodes.get(i);
}
protected static class Node {
private boolean visited;
private List<Integer> edges;
public Node() {
visited = false;
edges = new ArrayList<Integer>();
}
public void addEdge(int neighbour) {
edges.add(neighbour);
}
public List<Integer> getEdges() {
return Collections.unmodifiableList(edges);
}
public boolean wasVisited() {
return visited;
}
public void setVisited(boolean b) {
visited = b;
}
}
}