0

This is a simple dfs program calculating number of edges in component with vertex 1.

Test case: https://www.dropbox.com/s/4844zj7xnp4qw77/test.txt?dl=0 I don't know why it is giving a segmentation fault; please help me to solve this error.

#include<bits/stdc++.h>
using namespace std;
const int MXN = 1e6 + 2;

vector<int> adj[MXN];
int vis[MXN];
int n;
long long edges=0;
void dfs(int x) {
    edges+=adj[x].size();
    vis[x]=1;
    for (int i=0;i<adj[x].size();i++) {
        int y=adj[x][i];
        if ( !vis[y]) {
            dfs(y);
        }
    }
}
void solve() {
    cin >> n;
    for(int i=0;i<n-1;i++ ) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    cout<<edges/2<<endl;

}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(6);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t = 1;
    while (t--) {

        solve();

    }
}
Ankit Joshi
  • 21
  • 4
  • 5
    Consider the graph that is a linked list with one million elements, and how deep your recursion will get. – molbdnilo Jan 20 '21 at 12:48
  • Did you loaded this program to a debugger like gdb and repeated the test? This should give you the location. You should also be able to show the call stack and evaluate variables. – harper Jan 20 '21 at 12:48
  • yes gdb gives this error 0x0000000000401581 in dfs (x=47354) at C:\Users\hp\CLionProjects\untitled2\ankit.cpp:10 10 edges+=adj[x].size(); [Thread 13420.0x37dc exited with code 3221225725] [Thread 13420.0x2004 exited with code 3221225725] – Ankit Joshi Jan 20 '21 at 12:50
  • recursion will be about 2e5 for this test case .I think this is possible – Ankit Joshi Jan 20 '21 at 12:51
  • Input is a valid binary tree – Ankit Joshi Jan 20 '21 at 12:52
  • [Can't reproduce](https://godbolt.org/z/GKGxTz). Address sanitizer finds nothing when using data from link. How do you compile this? Which system/compiler its versions? What compiler flags did you used? – Marek R Jan 20 '21 at 12:54
  • But it is giving me above error.I am using windows gcc version 6.3.0c++17 – Ankit Joshi Jan 20 '21 at 12:59
  • `3221225725` indicates stack overflow error. Since my check is fine, changing some setting of compiler should fix the problem (increase stack limit). Or you can change algorithm to use `BFS` to avoid recursion. Do you compile for 32 bits or 64? Link I've provided uses 64 bit platform. – Marek R Jan 20 '21 at 13:00
  • how will I increase stack size. I used this set(CMAKE_EXE_LINKER_FLAGS "${CMAKE_EXE_LINKER_FLAGS} -Wl,--stack,10000000") but not working – Ankit Joshi Jan 20 '21 at 13:29
  • https://stackoverflow.com/questions/43326924/increasing-stack-size-for-c-program-in-clion this is taken from here – Ankit Joshi Jan 20 '21 at 13:30
  • 3221225725 = 0xC00000FD which is a very common magic number that you'll find on the internet – phuclv Jan 20 '21 at 14:19
  • Just change build process to Win64 and this should increase stack size. – Marek R Jan 20 '21 at 16:56
  • @MarekR the default stack size is [always 1MB on Windows](https://learn.microsoft.com/en-us/cpp/build/reference/stack-stack-allocations?view=msvc-160) regardless of target. You need to change the linker option to increase stack size – phuclv Jan 21 '21 at 02:23

1 Answers1

0

If you are using an unix based OS, try compiling after doing

ulimit -s unlimited

This sets your stack size to infinite and should eliminate overflow of stack buffer.

Arthur
  • 9
  • 1
  • 2