题目描述

关系

内容

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

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

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

输入格式

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

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

输出格式

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

否则输出 $-1$。

数据范围

$1\le n,m\le {10}^5$

输入样例：

3 3
1 2
2 3
1 3

输出样例：

1 2 3

问题分析

最初思路

思路分析

基于 BFS

定义一个数组 d，用来记录所有节点的入度，用队列来记录入度为 0 的节点。每次取出入度为 0 的节点，删除该节点即可。

基于 DFS

DFS 回溯之后输出的序列就是拓扑排序的逆序。因为，这意味着，当前节点所有的邻节点都已经遍历完了。那么当前节点当然应该是拓扑排序的最后一个节点。

假设，我们遍历到了最后一个节点（没有出度了），那么这个节点当然应该是拓扑排序的第一个节点。

DFS 如何判断拓扑排序是否成立呢？存在拓扑排序等价于有向图没有环。

DFS 如何判断图中有没有环呢？只有遍历过程中，没有遍历到路径上的点就行了。

从而我们只需要把 st 数组变为：

1. 0 表示没有遍历过；
2. 1 表示在当前递归过程中；
3. 2 表示已经遍历完了；

所以，如果我们在 dfs 过程中发现 st[j] == 1，就表示有环了。

执行流程设计

总结

代码实现

DFS

受到栈空间的限制。不一定能过。

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int N = 1e5 + 10;
int n, m;
vector<int> h[N];
int q[N], d[N], st[N];
int hh = 0, tt = -1;

bool dfs(int u) {
    st[u] = 1;
    
    for (auto v: h[u]) {
        if (!st[v] && !dfs(v)) {
            return false;
        } else if (st[v] == 1) return false;
    }
    
    st[u] = 2;
    
    q[++tt] = u;
    
    return true;
}

bool topsort() {
    for (int i = 1; i <= n; i++) {
        if (!st[i] && !dfs(i)) return false;
    }
    return true;
}

int main()
{
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        d[b]++;
        h[a].pb(b);
    }
    
    if (!topsort()) puts("-1");
    else {
        for (int i = n - 1; i >= 0; i--) cout << q[i] << " ";
    }
    return 0;
}

BFS

这是一般解法。

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int N = 1e5 + 10;
int n, m;
vector<int> h[N];
int q[N];
int d[N];

bool topsort() {
    // 将所有入度为0的点加入队列
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++) {
        if (!d[i]) q[++tt] = i;
    }
    
    while (hh <= tt) {
        int t = q[hh++];
        
        for (auto v: h[t]) {
            // 删除所有入度即将为0的节点
            if (--d[v] == 0) {
                q[++tt] = v;
            } 
        }
    }
    // 如果最后队尾为n-1，意味着，所有节点都入队过，故无环，存在拓扑序列
    return tt == n - 1;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        d[b]++;
        h[a].pb(b);
    }

    if (!topsort()) puts("-1");
    else {
        // 输出所有'曾经'入队过的序列
        for (int i = 0; i < n; i++) {
            cout << q[i] << " ";
        }
    }
    return 0;
}