給定一個n個點m條邊的有向圖，圖中可能存在重邊和自環，
請輸出任意一個該有向圖的拓撲序列，如果拓撲序列不存在，則輸出-1，
若一個由圖中所有點構成的序列A滿足：對于圖中的每條邊(x, y)，x在A中都出現在y之前，則稱A是該圖的一個拓撲序列，
輸入格式
第一行包含兩個整數n和m
接下來m行，每行包含兩個整數x和y，表示存在一條從點x到點y的有向邊(x, y)，
輸出格式
共一行，如果存在拓撲序列，則輸出拓撲序列，
否則輸出-1，
資料范圍
1≤n,m≤1051≤n,m≤105
輸入樣例：
3 3
1 2
2 3
1 3
輸出樣例：
1 2 3
import java.util.ArrayDeque; import java.util.Arrays; import java.util.Scanner; public class Main{ static final int N=100005; static int e[]=new int[N*2];//題目要求說了，可能出現重邊和自環 static int ne[]=new int[N*2]; static int h[]=new int[N]; static int d[]=new int[N]; static int v[]=new int[N];//存盤拓撲序列 static int n,m,idx; static ArrayDeque<Integer> q=new ArrayDeque<Integer>(); static void add(int a,int b){ e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } static void topsort(){ int k=0; for(int i=1;i<=n;i++) if(d[i]==0) q.offer(i); while(!q.isEmpty()){ int t=q.poll(); v[k++]=t; for(int i=h[t];i!=-1;i=ne[i]){ int j=e[i]; d[j]--;//重路和自環都可以解決 if(d[j]==0) q.offer(j); } } if(k==n) for(int i=0;i<k;i++) System.out.print(v[i]+" "); else System.out.println("-1"); } public static void main(String[] args) { Scanner scan=new Scanner(System.in); n=scan.nextInt(); m=scan.nextInt(); Arrays.fill(h, -1); while(m-->0){ int a=scan.nextInt(); int b=scan.nextInt(); add(a,b); d[b]++; } topsort(); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/96534.html
標籤：其他