1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
| import java.io.*; import java.util.*; public class Main {
public static void main(String[] args) { FastScanner sc=new FastScanner(); PrintWriter pw=new PrintWriter(System.out); TopSort ts=new TopSort(); while(sc.hasNext()){ int n=sc.nextInt(); int m=sc.nextInt(); ts.init(); for(int o=1;o<=m;o++){ int a=sc.nextInt(); int b=sc.nextInt(); ts.add_diredge(a-1, b-1, 1); } ts.sort(n); for(int i=0;i<ts.st;i++){ if(i==ts.st-1)pw.println(ts.res[i]+1); else pw.print((ts.res[i]+1)+" "); } pw.flush(); } }
} class TopSort{ int[]head; Edge[]edge; int cnt; int maxn=10050; int maxm=20050; int st; int[]du; int[]res; PriorityQueue<Integer>queue; TopSort(){ head=new int[maxn]; edge=new Edge[maxm]; for(int i=0;i<maxm;i++)edge[i]=new Edge(); du=new int[maxn]; res=new int[maxn]; queue=new PriorityQueue(); } void init(){ queue.clear(); Arrays.fill(head,-1); st=0; cnt=0; } void sort(int n){ for(int i=0;i<n;i++){ if(du[i]==0)queue.add(i); } while(!queue.isEmpty()){ int u=queue.poll(); res[st++]=u; for(int i=head[u];i!=-1;i=edge[i].next){ int to=edge[i].to; du[to]--; if(du[to]==0)queue.add(to); } } } void add_diredge(int u,int v,int w){ edge[cnt].to=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++; du[v]++; } } class Edge{ int to,next,w; }
|