Pagini recente » Cod sursa (job #3325051) | Cod sursa (job #1882443) | Cod sursa (job #1878567) | Cod sursa (job #1705831)
import java.util.*;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
class Main {
static List<List<Integer>> graph;
static boolean visited[];
static int indegree[];
static int N;
static void topSort() throws FileNotFoundException {
List<Integer> res = new ArrayList<>();
Stack<Integer> s = new Stack<>();
for (int u = 1; u <= N; u++)
if(indegree[u] == 0) {
s.push(u);
}
int u;
while (!s.isEmpty()) {
u = s.pop();
res.add(u);
List<Integer> successors = graph.get(u);
for (Integer v : successors) {
indegree[v]--;
if (indegree[v] == 0) {
s.push(v);
}
}
}
PrintWriter output = new PrintWriter("sortaret.out");
for(Integer i : res)
output.print(i + " ");
output.close();
}
static void init_graph(int n) {
graph = new ArrayList<>();
for (int i = 0; i <= n; i++)
graph.add(new ArrayList<Integer>());
}
public static void main(String[] args) throws IOException {
Scanner input = new Scanner(new FileReader("sortaret.in"));
N = input.nextInt();
int M = input.nextInt();
indegree = new int[N + 1];
init_graph(N);
int node1, node2;
for (int i = 0; i < M; i++) {
node1 = input.nextInt();
node2 = input.nextInt();
graph.get(node1).add(node2);
indegree[node2]++;
}
topSort();
input.close();
}
}