AcWing 848. 有向图的拓扑序列-java
原题链接
简单
作者:
Susu
,
2020-01-29 21:51:11
,
所有人可见
,
阅读 788
import java.util.*;
public class Main{
static int N = 100010;
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int n,m;
static int idx;
static int[] q = new int[N];
static int[] d = new int[N];
static boolean topSort(){
int hh=0,tt=-1;
for(int i=1;i<=n;i++){
if(d[i]==0){
q[++tt]=i;
}
}
while(hh<=tt){
int t = q[hh++];
for(int i=h[t];i!=-1;i=ne[i]){
int j = e[i];
d[j]--;
if(d[j]==0) q[++tt]=j;
}
}
return tt == n-1;
}
static void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i=0;i<N;i++){
h[i]=-1;
}
while(m-->0){
int x = sc.nextInt();
int y = sc.nextInt();
add(x,y);
d[y]++;
}
if(topSort()){
for(int i=0;i<n;i++){
System.out.print(q[i]+" ");
}
}else{
System.out.print("-1");
}
}
}