UVA10305 Ordering Tasks 题解 (拓扑排序模板)

预备知识

• 开始学图论了，紫书上拓扑排序的入门题，在洛谷找到了它拿来练手。
• 一篇关于拓扑排序的很透彻的博客，如果你还不了解拓扑排序，可以看完了再回来刷这条题目。

题意翻译

John有n个任务要做，每个任务在做之前要先做特定的一些任务。

输入第一行包含两个整数n和m，其中1<=n<=100。 n表示任务数，而m表示有m条任务之间的关系。 接下来有m行，每行包含两个整数i和j，表示任务i要在j之前做。

当读入两个0（i=0，j=0）时，输入结束。

输入输出样例

输入样例#1：

5 4
1 2
2 3
1 3
1 5
0 0

输出样例#1：

1 4 2 5 3

输出包含q行，每行输出一条可行的安排方案。

分析

1. 拓扑排序有两个经典算法kahn算法和基于dfs的算法，这里我们采取后者。
2. 先说说坑点，这题有多组输入，不要被样例的一组给骗了。
3. 题目没说无解的情况怎么输出，大概就是无解输出-1。
4. 首先如果存在环路，那么拓扑排序就无法进行，那么如何判断环路呢，我们可以用一个vis数组记录每个点的访问状况，值为-1时表示正在访问，如果递归时重复的遇到这个状态就说明存在环路，为0时表示还没有访问，为1时表示已经访问过了。
5. 用一个topo数组记录答案，记录答案时要从后往前，想一想为什么(提示：递归)

代码

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 110;
/* top数组的指针，用于从后往前记录答案
 * G 邻接矩阵存图
 */
int n, m, top;
int G[maxn][maxn], vis[maxn];

bool dfs(int u){
    vis[u] = -1;
    for (int j = 1; j <= n; ++j){
        if (G[u][j]){
            if (vis[j] < 0)
                return false;
            else if (!vis[j] && !dfs(j))
                return false;
        }   
    }
    vis[u] = 1;
    topo[top--] = u;
    return true;
}

bool topo_sort(){
    top = n;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; ++i){
        if (!vis[i] && !dfs(i))
            return false;
    }
    return true;
}

int main(int argc, char const *argv[]){
    while (scanf("%d%d", &n, &m) == 2 && n){
        int u, v;
        for (int i = 1; i <= m; ++i){
            scanf("%d%d", &u, &v);
            G[u][v] = 1;
        }
        if (!topo_sort()){
            printf("%d ", -1);
        }else {
            for (int i = 1; i <= n; ++i)
                printf("%d ", topo[i]);
        }
        printf("\n");
    }
    return 0;
}