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

Question

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

无论如何，我花了将近 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");
}

提前致谢，笔尖

Answer 1

您的 DFS 仅检查图中的一个连接组件：包含金属 0 的组件。您不能假设存在从该金属到所有其他金属的路径。

此外，当您检测到 您之前见过的顶点（它可能是也可能不是循环的一部分 - 但无论如何，问题描述中已经告诉您输入中不能出现循环）。您没有测试正确的条件。

Answer 2

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

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

How come TopoSort only works on certain graphs, and fails on others?

c++

algorithm

debugging

graph-theory

graph-algorithm