c++ - 为什么 TopoSort 仅适用于某些图形，而对其他图形无效？

Question

我最近学习了拓扑排序算法以及如何使用 dfs 和堆栈来实现它，所以我编写了一个问题的解决方案 Reactivity Series并直接实现拓扑排序。但我不确定为什么它在测试用例 #4 上得到错误答案。测试用例不公开，所以我什至不知道哪个测试用例不好。

无论如何，我花了将近 1/2 小时来尝试纠正我的解决方案、创建测试用例等，但没有取得太大进展。任何有关调试的帮助将不胜感激。代码如下:

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

vvi graph;
vector<bool> flag;
stack<int> topo;

#define sz(C) int((C).size())

void dfs(int i)
{
    if(!flag[i])
    {
        flag[i] = true;
        for(vi::iterator it = graph[i].begin();it != graph[i].end();it++)
        {
            if(flag[*it])
            {
                printf("back to the lab\n");
                exit(0);
            }
            else
            {
                dfs(*it);
            }
        }
        topo.push(i);
    }
}

int main(void)
{
    int n, k, a, b;
    scanf("%d%d", &n, &k);
    graph.clear(); graph.resize(n); flag.resize(n, false);
    for(int i = 0;i < k;i++)
    {
        scanf("%d%d", &a, &b);
        graph[a].push_back(b);
    }

    dfs(0);

    while(!topo.empty())
    {
        printf("%d ", topo.top());
        topo.pop();
    }
    printf("\n");
}

提前致谢， Nib

Answer 1

您的代码将始终首先打印 0。请注意，不难想到没有以 0 作为第一个元素的有效拓扑排序的情况。