$$\color{Red}{有向图的拓扑序列——详细解析——三种语言}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思路

有向无环图一定存在拓扑序列

一个长度为N的序列，如果将它排列后从前往后的每条边都指向它之后的边不会指到之前的边，称其为拓扑序列
我们可以定义一个d[N]的数组存放“入度”——指向该点的个数，并定义一个队列并将每个入度为0的点放入队列
for(int i = h[t]; i != -1; i = ne[i]){
    int u = e[i];
    if(--d[u] == 0)
    q[++tt] = u;
} 
这么操作的意义是不存在环的情况下每个点都会入队，如果出现环，必然经过一轮递减之后，没有入度为0的点

java 代码

import java.util.*;

public class Main {
    static int N = 100010, n, m, idx = 0;
    static int e[] = new int [N];
    static int ne[] = new int [N];
    static int r[] = new int [N];
    static int h[] = new int [N];
    static int q[] = new int [N];

    public static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
        r[b] ++;
    }

    public static void topsort(){
        int hh = 0, tt = -1;
        for(int i=1; i<=n; i++) 
            if (r[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];
                r[j] --;
                if (r[j] == 0) q[++tt] = j;
            }
        }
        if (tt == n-1) 
            for(int i = 0; i < n; i++)
                System.out.print(q[i] + " ");
        else    
            System.out.println(-1);
    }

    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 a = sc.nextInt(), b = sc.nextInt();
            add(a, b);
        }

        topsort();
    }
}

python3 代码

N = 100010
e = [0] * N #邻接表
ne = e.copy()
d = e.copy()
h = [-1] * N
idx = 0
q = [0] * N  #队列


def add(a, b):
    global idx
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    d[b] += 1
    idx += 1

def topsort():

    hh, tt = 0, -1  #手动模拟队列->本题最后是将整个队列输出 
    for i in range(1,n+1):
        if d[i] == 0:
            tt += 1
            q[tt] = i
    #广度搜索
    while hh <= tt:
        t = q[hh]
        hh += 1
        i = h[t]
        while i != -1:
            j = e[i]
            d[j] -= 1
            if d[j] == 0:
                tt += 1
                q[tt] = j
            i = ne[i]
    #布尔值的返回结果，是否所有点都遍历到
    #若存在环，注定环内的点无法进入队列
    return tt == n-1

if __name__ == '__main__':
    n, m = map(int, input().split())
    for i in range(m):
        a, b = map(int, input().split())
        add(a, b)
    if topsort():
        for i in range(n):
            print(q[i], end = ' ')
    else:
        print('-1')

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
int e[N], ne[N], h[N], idx;
int q[N], d[N];
int n, m;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool topsort()
{
    int hh = 0, tt = -1;
    //我们要找到所有入度为0的点，但是显然我们无法通过
    //链表的遍历去找——邻接表数据是分布存储
    //那么我们可以通过遍历有头有尾的入度表的下标
    for(int i = 1; i<=n; i++)
        if(!d[i]) 
            q[++tt] = i;
    //此时我们已经把入度为一的点全部存储完毕
    //依次删除他们指向的边，指向点入度若为0，此时说明
    //该点又是新起点，入队列，如果不为0，说明是环
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int u = e[i];
            if(--d[u] == 0)
                q[++tt] = u;
        }
    }
    return tt == n-1;
}

int main()
{
    //链表初始化，其实不初始化也行，此时尾结点为0
    memset(h, -1, sizeof h);
    int a, b;
    scanf("%d%d", &n, &m);
    while(m--)
    {
        scanf("%d%d", &a, &b);
        add(a,b);
        //a连向b，那么b的入度显然要加1
        d[b] ++;
    }
    if(topsort())
        for(int i=0; i<n; i++)  printf("%d ", q[i]);
    else
        printf("-1\n");
    return 0;
}