博客

拓扑序列：

拓扑序是按照点的先后顺序排列的。拓扑序列满足以下两点：

1.每个顶点在序列中出现且只出现一次。

2.若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

拓扑序列只存在于有向无环图中。可以理解成一个将图进行层序遍历后的序列（宽搜）。所以拓扑序列可能有多个。

例如：

用宽搜找出图的一个拓扑序列：

大致分为如下两步：

1.将入队为0的点入队；

2.更新队列中点的出度；

3.重复上述两步直到队列为空。

最后我们发现，依次出队的点就组成了一个拓扑序列。

用邻接矩阵存储图，并且用数组录每个点的入队。

输入格式：

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

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

输出格式：

共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。否则输出-1。

代码如下：
 

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int e[N], ne[N], h[N], idx = 0;//邻接表
int q[N], hh = 0, tt = -1;//队列
int pre[N];//入度
int n, m;

void add(int a, int b) {
    pre[b]++;//入度加一
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
    return;
}

int topsort() {
    for (int i = 1; i <= n; i++)//入度为0的入队
        if (!pre[i])q[++tt] = i;

    while (hh <= tt) {//队列不空
        int t = q[hh++];//取出队头

        for (int i = h[t]; i != -1; i = ne[i])//更新队头点的出度
            if (--pre[e[i]] == 0)q[++tt] = e[i];
    }

    if (tt == n - 1)return 1;
    return 0;

}

int main() {
    memset(h, -1, sizeof h);//初始化邻接表
    cin >> n >> m;
    int a, b;
    while (m--) {
        cin >> a >> b;
        add(a, b);
    }

    int t = topsort();
    if (t == 0)cout << "-1";
    else {//输出队列
        for (int i = 0; i <= tt; i++)
            cout << q[i] << " ";
    }
    return 0;
}