深度优先搜索的替代算法

Question

一个问题涉及在有向图中进行深度优先搜索，以找到可以从特定节点到达的所有节点。下面给出的解决方案在 codechef 上给出了错误的结果。但是我找不到任何可能产生与通常的 DFS 算法不同的结果的测试用例。

我知道我可以直接执行正确的算法来获得正确的结果，但我想了解为什么我的解决方案不正确，以便以后不再重复。请帮我确定这个解决方案有什么问题。注释代码以解释我的方法

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long int lli;
vector <lli> g[1000+5]; // the adjacency list 1 indexed
void dfs(lli j, lli i);

int main(){
    lli n, m, k, a, b;
    // n = number of nodes
    // m = number of relations
    // k = multiplication factor
    cin >> n >> m >> k;
    while(m--){
        // a,b means a is dependent upon b (directed graph)
        cin >> a >> b;
        g[a].push_back(b);
    }

    for(lli j = 1; j <= n; j++)
    for(lli i = 0; i < g[j].size(); i++){
        dfs(j, g[j][i]); // adds dependencies of g[j][i] 
                         // to adjacency list of j
    }

    // ans is the minimum no of nodes dependent on a particular node
    lli ans = g[1].size();
    for(lli i = 1; i <= n; i++){
        if(g[i].size() < ans)
        ans = g[i].size();
    }

    cout << (ans+1)*k <<"\n";
}

void dfs(lli j, lli i){
    // adding dependencies of a node to itself 
    // would result in an infinite loop?
    if(i != j){
        for(lli k = 0; k < g[i].size(); k++){
            // a node is not dependent on itself
            if(g[i][k]!=j && find(g[j].begin(), g[j].end(), g[i][k])==g[j].end()){
            g[j].push_back(g[i][k]);
            dfs(j, g[i][k]);
            }
        }       
    }
}`

link的问题：problem

link 正确的解决方案：correct solution

Answer 1

你的问题是你不知道在给定的问题约束下可能存在的多边，否则它看起来是正确的。看看这个测试用例：

你的程序会return3个，但是只有2个顶点！

话虽如此，我想补充一点，我不同意示例解决方案：它说运行时间将是 O(N^2) 这不是真的，因为它开始于 N dfs 每个成本为 O(N+M) 因此导致 O(N*(N+M)) 与 N=10^3 和 M=10^6 在 0.01 秒的时间限制内没有变化！

实际上，这个问题可以在 O(N+M) 中使用检测强连通分量的算法来解决。

深度优先搜索的替代算法

Alternative algorithm for depth first search

c++

depth-first-search