Pagini recente » Cod sursa (job #3199019) | Cod sursa (job #2694887) | Rating Jecan Stefan Calin (Alpin) | Cod sursa (job #434727) | Cod sursa (job #1870035)
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
Reader in = new Reader(new FileInputStream("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);
}
List<Integer> sorted = TopologicalSort.topSort(graph);
BufferedWriter out = new BufferedWriter(new FileWriter("sortaret.out"));
for (int i : sorted) {
out.write((i + 1) + " ");
}
out.close();
}
private static class Reader {
private BufferedInputStream stream;
private byte[] buffer;
int buffSize;
private int buffPointer;
protected final int BUFF_CAPACITY = 5000;
protected Reader(FileInputStream file) {
stream = new BufferedInputStream(file);
buffer = new byte[BUFF_CAPACITY];
buffPointer = buffSize = 0;
}
private void fillBuffer() throws IOException {
buffSize = stream.read(buffer, 0, BUFF_CAPACITY);
buffPointer = 0;
}
private byte readByte() throws IOException {
if (buffPointer >= buffSize) {
fillBuffer();
}
return buffer[buffPointer++];
}
protected int nextInt() throws IOException {
byte b = readByte();
while (b < '0' || b > '9') {
b = readByte();
}
int num = 0;
while (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
b = readByte();
}
return num;
}
}
}
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 edges;
}
public boolean wasVisited() {
return visited;
}
public void setVisited(boolean b) {
visited = b;
}
}
}