题目描述

算法分析

时间复杂度 $O(n + m)$

参考文献

算法基础课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main{
    static int N = 100010;
    static int n;
    static int m;
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int idx = 0;
    static int[] d = new int[N];//记录每个点的入度个数
    static int[] qv = new int[N];//记录队列进入的元素
    static int qidx = 0;
    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static boolean topsort()
    {
        Queue<Integer> q = new LinkedList<Integer>();
        //将所有入度为0的点进去队列
        for(int i = 1;i <= n;i++)
        {
            if(d[i] == 0)
            {
                q.add(i);
                qv[qidx ++] = i;
            }

        }
        while(!q.isEmpty())
        {
            int t = q.poll();
            //枚举t的所有出边
            for(int i = h[t];i != -1;i = ne[i])
            {
                int j = e[i];

                //删除当前出边
                d[j] --;
                if(d[j] == 0)
                {
                    q.add(j);
                    qv[qidx ++] = j;
                }

            }
        }
        return qidx == n ;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = reader.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            String[] s2 = reader.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            add(a,b);

            d[b] ++;
        }
        if(topsort())
        {
            for(int i = 0;i < n;i++) System.out.print(qv[i] + " ");
        }
        else System.out.println("-1");
    }
}

扩展:如何输出字典序最小的序列

• 将队列换成优先队列，优先队列取出的元素是当前字典序最小的编号，在出队的时候记录出队的编号即为当前字典序最小的拓扑序

时间复杂度 $O(logn*(n + m))$

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.PriorityQueue;

public class Main{
    static int N = 100010;
    static int n;
    static int m;
    static int[] d = new int[N];
    static int[] qv = new int[N];
    static int qidx = 0;
    static int[] h = new int[N];
    static int[] ne = new int[N];
    static int[] e = new int[N];
    static int idx = 0;
    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static boolean topsort()
    {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();

        for(int i = 1;i <= n;i ++)
        {
            if(d[i] == 0) 
            {
                q.add(i);

            }
        }

        while(!q.isEmpty())
        {
            int t = q.poll();
            qv[qidx ++] = t;
            for(int i = h[t];i != -1;i = ne[i])
            {
                int j = e[i];

                d[j] -- ;

                if(d[j] == 0)
                {
                    q.add(j);
                }

            }
        }

        return qidx == n;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            add(a,b);
            d[b] ++;
        }
        if(topsort()) for(int i = 0;i < qidx;i ++) System.out.print(qv[i] + " ");
        else System.out.println("-1");
    }
}