AcWing 848. 有向图的拓扑序列
原题链接
简单
Java代码
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
List<List<Integer>> g = new ArrayList<>();
int[] d = new int[n + 1];
for(int i = 0; i <= n; i ++){
g.add(new ArrayList());
}
for(int i = 0; i < m; i ++){
int a = sc.nextInt(), b = sc.nextInt();
g.get(a).add(b);
d[b] ++;
}
List<Integer> res = new ArrayList<>();
Deque<Integer> deq = new LinkedList<>();
for(int i = 1; i <= n; i ++){
if(d[i] == 0){
deq.offer(i);
}
}
int cnt = 0;
while(!deq.isEmpty()){
int t = deq.poll();
res.add(t);
cnt ++;
for(int i: g.get(t)){
if(--d[i] == 0){
deq.offer(i);
}
}
}
if(cnt != n) System.out.println(-1);
else{
for(int num: res){
System.out.printf("%d ", num);
}
}
}
}