题目描述

给定一个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

算法1

(暴力枚举)

首先把遍历一遍，将所有入度为 0 的点压入队列中，再就是bfs 的经典操作： 只要队列不空， 取出队头元素，遍历所有出边，并且将该点的入度减一， 若为 0， 则压入队列中。
$\color{red}{例如：}$ x -> y; 从队列中取出 x 后， 由于 x 的出边连着 y， 则将 y 的入度减一

时间复杂度

$O(n^2)$

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
 using namespace std;

const int N = 100010;
int e[N], ne[N], h[N], idx;
bool st[N];
int in[N]; //入度
vector<int> v; //存取结果
int n, m;
queue<int> q;

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

void topsort()
{
    while(q.size())
    {
        int t = q.front();
        q.pop();
        v.push_back(t);
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            in[j] --;
            if(!in[j]) q.push(j);
        }
    }

    if(v.size() == n) for(int i = 0; i < v.size(); i++) printf("%d ", v[i]);
    else cout<<"-1";
}
 int main()
 {
     memset(h, -1, sizeof h);
     cin>>n>>m;
     int a, b;
     while(m--)
     {
         scanf("%d%d", &a, &b);
         add(a, b);
         in[b] ++;
     }

     for(int i = 1; i <=n; i++)
     {
         if(!in[i]) q.push(i);

     }

     topsort();
 }