AcWing 848. 有向图的拓扑序列
原题链接
简单
作者:
autumn_0
,
2025-01-06 13:12:37
,
所有人可见
,
阅读 2
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] d = new int[n + 1];
int cnt = 0;
List<Integer> res = new ArrayList<>();
List<List<Integer>> g = new ArrayList<>();
for(int i = 0; i <= n; i ++ ) g.add(new ArrayList<>());
for(int i = 1; i <= m; i ++ ){
int a = sc.nextInt();
int b = sc.nextInt();
g.get(a).add(b);
d[b] ++ ;
}
Deque<Integer> q = new LinkedList<>();
for(int i = 1; i <= n; i ++ )
if(d[i] == 0) q.offer(i);
while(q.size() != 0){
int t = q.poll();
cnt ++ ;
res.add(t);
for(int e: g.get(t)){
if(-- d[e] == 0) q.offer(e);
}
}
if(cnt == n){
res.forEach(item -> System.out.print(item + " "));
} else System.out.println(-1);
}
}