848. 有向图的拓扑序列（模板）

佚名 6年前 (2020-02-03) 算法 1286人围观抢沙发百度已收录

给定一个n个点m条边的有向图，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。

输入格式

第一行包含两个整数n和m

接下来m行，每行包含两个整数x和y，表示存在一条从点x到点y的有向边(x, y)。

输出格式

共一行，如果存在拓扑序列，则输出拓扑序列。

否则输出-1。

数据范围

1≤n,m≤1051≤n,m≤105

输入样例：

输出样例：

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();
        }
}