题目描述

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

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

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

输入格式

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

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

输出格式

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

否则输出-1。

数据范围

1≤n,m≤105

输入样例

3 3
1 2
2 3
1 3

输出样例

1 2 3

思路

有向图才会有拓扑序列

有环图是不存在拓扑序列的

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

入度：有多少条边指向自己

出度：有多少条边出去

入度为0的点：排在当前最前面的位置

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=1e5+10;

int n,m;                  //n代表结点个数，m代表边数
int h[N],e[N],ne[N],idx;  //h[]是链表头，e[]存储当前结点的元素，ne[]存储当前结点的下一个结点的位置,idx表示现在已经用到了哪个结点
int q[N],d[N];            //q[]模拟队列，存储入度为0的所有数（有顺序），d[]存储每个点的入度

void add(int a,int b)     //将b插入a链表，详情请看yxc的单链表讲解视频（视频网址在下方）
{
    e[idx]=b;             //将b的值存进当前这个结点
    ne[idx]=h[a];         //将当前结点的next指针指向头结点h[a]所指向的结点
    h[a]=idx;             //将头指针h[a]指向的结点变为当前这个结点
    idx++;                //当前点已经用到，让idx指向下一个还没有用到的点
}

bool pd()                 //输出是否存在拓扑排序
{
    int hh=0,tt=-1;       //用数组模拟队列，详情请看yxc模拟队列讲解视频（视频网址附下），定义头指针hh和尾指针tt，因为后面以tt++为主，

    for(int i=1;i<=n;i++) //先将每一个数值遍历一遍，看看哪个数值的入度是0，说明它排在当前最前面的位置，便把它放到q数组里
    {
        if(d[i]==0)     
           q[++tt]=i;
    }

    while(hh<=tt)         //如果队列不是空的
    {
        int t=q[hh++];    //用数字t存下头结点的值,头结点向后走一位

        for(int i=h[t];i!=-1;i=ne[i])  //邻接表查询方式，查询每个以t为链表头的链表
        {
            int j=e[i];                //用j存下当前结点的值
            d[j]--;                    //因为这个点一定是连接表头有边相连，所以将这个点的入度删掉1，看看它是否是与它相连的点的最前面的位置
            if(d[j]==0) q[++tt]=j;     //如果是，把它也存进q数组里
        }
    }

    if(n-1==tt) return true;           //如果q数组里的数的个数和n相等（因为tt从0开始计数，n从1开始计数，所以n-1=tt） 那么说明所有q数组的数就是拓扑序列
}

int main()
{
    scanf("%d%d",&n,&m);               //输入结点个数n和多少条边m
    memset(h,-1,sizeof h);             //将每个链表头初始化，指向-1

    for(int i=0;i<m;i++)               //循环m次输入m条边
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b); 
        d[b]++;                        //因为是点a指向点b，所以b的入度+1
    }

    if(pd()==true)
    {
        for(int i=0;i<n;i++) printf("%d ",q[i]); //因为q数组的存储就是按照邻接表查询的顺序存储的，所以如果是拓扑序列，那么就从0到n-1按顺序输出所有q数组的数
    }
    else printf("-1");                 //如果不存在就输出-1

    return 0;
}

附：

yxc单链表讲解视频
yxc模拟队列讲解视频