实现图DFS求连通分量最小和时遇栈溢出错误求助

Hey there! Let's break down why your DFS code is causing a stack overflow and fix it step by step.

The Key Issues in Your Code #

Let's go through the critical bugs that are leading to the overflow:

1. Infinite Recursion Due to Wrong Node in DFS Call
   In your loop over the neighbors of node x, you're calling DFS(x, ...) instead of passing the neighbor node graph[x][n]. This means you're recursively calling DFS on the same node over and over again—no wonder the stack gets crushed!

2. Passing Containers by Value Instead of Reference
   Your DFS function takes graph, cost, and visited as value parameters. Every time you recurse, the program makes full copies of these vectors. Not only is this super inefficient, but the visited array's changes are only made to the copy—so the original visited in the parent call never knows that a node was marked as visited. This leads to repeated visits to the same nodes, adding more recursive calls to the stack.

Fixed Code #

Here's the corrected version with explanations of the changes:

#include <bits/stdc++.h>
using namespace std;

// Changed parameters to references to avoid copies and propagate visited changes
void DFS(int x, const vector<vector<int>>& graph, const vector<int>& cost, vector<bool>& visited, int &c) {
    c = min(c, cost[x]);
    visited[x] = true;
    for (int neighbor : graph[x]) { // Range-based for loop for cleaner code
        if (!visited[neighbor])
            DFS(neighbor, graph, cost, visited, c); // Call DFS on the neighbor, not x!
    }
}

void solve() {
    int nodes, edges;
    cin >> nodes >> edges;
    vector<int> cost(nodes);
    vector<bool> visited(nodes, false); // Initialize visited to false explicitly
    vector<vector<int>> graph(nodes);
    
    for (int i = 0; i < nodes; i++)
        cin >> cost[i];
    
    for (int i = 0; i < edges; i++) {
        int a, b;
        cin >> a >> b;
        graph[a - 1].push_back(b - 1);
        graph[b - 1].push_back(a - 1);
    }
    
    int ans = 0;
    for (int i = 0; i < nodes; i++) {
        if (!visited[i]) {
            int c = cost[i];
            DFS(i, graph, cost, visited, c);
            ans += c;
        }
    }
    cout << ans << "\n";
}

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

What Changed? #

• Reference Parameters: graph, cost (const, since we don't modify them), and visited are now passed as references (&). This avoids copying large vectors and ensures that visited updates are shared across all recursive calls.
• Fixed Recursive Call: We now pass neighbor (the current adjacent node) to the DFS call instead of x, so we actually traverse the graph instead of looping on the same node.
• Explicit Visited Initialization: Added false to vector<bool> visited(nodes, false) to make the initialization clear (though in C++ default initialization for bool vectors is false, this is just for readability).

Why This Fixes the Stack Overflow #

By fixing the recursive call target, we stop the infinite loop of calling DFS on the same node. Using references ensures that we don't create unnecessary copies, and more importantly, the visited array correctly tracks which nodes have been processed—so we don't reprocess nodes and add extra recursive calls to the stack.

内容的提问来源于stack exchange，提问作者ganpa