Pagini recente » Cod sursa (job #2827321) | Cod sursa (job #2035811) | Cod sursa (job #3188483) | Cod sursa (job #2524225) | Cod sursa (job #1239773)
import java.io.*;
import java.util.*;
class FastScanner {
private BufferedReader br;
private StringTokenizer st;
public FastScanner(InputStream stream) {
br = new BufferedReader(new InputStreamReader(stream));
}
private String next() {
while (st == null || !st.hasMoreTokens()) {
String line = null;
try {
line = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
if (line == null)
return null;
st = new StringTokenizer(line);
}
return st.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
public class Main {
private static List<List<Integer>> G;
private static int V;
private static void DFS(final int x, final boolean[] visited, final List<Integer> topologicalSort) {
visited[x] = true;
for (int y: G.get(x))
if (!visited[y])
DFS(y, visited, topologicalSort);
topologicalSort.add(x);
}
private static void addEdge(final int from, final int to) {
G.get(from).add(to);
}
private static List<Integer> getTopologicalSort() {
boolean[] visited = new boolean[V];
List<Integer> topologicalSort = new ArrayList<Integer>();
for (int x = 0; x < V; ++x)
if (!visited[x])
DFS(x, visited, topologicalSort);
Collections.reverse(topologicalSort);
return topologicalSort;
}
public static void main(String[] args) throws IOException {
FastScanner reader = new FastScanner(new FileInputStream("sortaret.in"));
V = reader.nextInt();
G = new ArrayList<List<Integer>>(V);
for (int x = 0; x < V; ++x)
G.add(new ArrayList<Integer>());
int edgeCount = reader.nextInt();
for (; edgeCount > 0; --edgeCount) {
int x = reader.nextInt() - 1;
int y = reader.nextInt() - 1;
addEdge(x, y);
}
List<Integer> topologicalSort = getTopologicalSort();
PrintWriter writer = new PrintWriter("sortaret.out");
for (int x: topologicalSort)
writer.write((x + 1) + " ");
writer.write("\n");
writer.close();
}
}