c++ - 因超时而终止？如何提高 DFS

Question

我尝试了一个hackerrank问题链接，由于3个测试用例超时，我被终止了。在那里，我使用了 dfs 方法来检查连接的组件并使用每个不相交元素的乘积之和获得 ans。（a b + a c + a d + b c + b d + c d == a*b + ( a+b)*c + (a+b+c)*d)。我需要知道我的 dfs 出了什么问题 ;{( 以及如何改进这一点。我不需要解决hackerrank 问题。只需要知道我的错误是什么。

这是我的代码。谢谢

#include <iostream>
#include <vector>

using namespace std;

#define For(i,a,n) for (int i=a; i<n; i++)
typedef vector<int> vi;

// returns no. of connected nodes to a given node
int connected(int node, vector<vi> adj, bool visited[]){
    int count = 0;
    for(auto x: adj[node]){
        if(visited[x]) continue;
        visited[x] = true;
        count += connected(x, adj, visited) + 1;
    }
    return count;
}

void dfs(int nodes, vector<vi> adj, bool visited[]){
    int ans = 0;
    visited[nodes] = true;
    int current_sum = connected(nodes, adj, visited) + 1;

    while(nodes--){
        if(visited[nodes]) continue;
        visited[nodes] = true;
        int out = connected(nodes, adj, visited) + 1;
        ans += current_sum*out;
        current_sum += out;    
    }
    cout<< ans;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int a,b,edges,nodes;
    cin>>nodes>>edges;
    bool visited[nodes];
    fill(visited, visited + nodes, 0);
    vector<vi> adj(nodes);

    // adj[i] gives the directly connected nodes to i
    while(edges--){
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs(nodes-1, adj, visited);
    return 0;
}

标签： c++algorithmgraph-theorydepth-first-search