Implementing DFS, works fine with shorter inputs but, throw segmentation error with larger inputs

Question

This code that I am writing is to detect SCCs in a graph, it is the first programming assignment of "stanford graphs and data structures" but, with large inputs it throws exception errors. I have tried it with different IDEs and all the time I get segmentation fault with larger inputs. I would really like to find out the problem and how to fix that, I willing to change my approach if that is the problem. I am almost sure that this is maybe due to filling of dynamic storage. Here is the code:

#include<vector>
#include<map>
#include<iostream>
#include<algorithm>
#include<fstream>
#define lli long long int
#define usi unsigned short int
using namespace std;
struct node {
    vector<int> edge_index;
    bool detected;
    int leader;
};
vector<node> nodes;
vector<pair<int, int>> edges;
map<int, vector<int>> SCC;
vector<int> finish_time, SCC_size;
int count_t, lead;
bool rev = false;
void DFS(int start) {
    //int size = nodes.size();
    nodes[start].detected = true;
    static int c = 0;
    c++;
    //int size1 = nodes.size();
    for (int i = 0; i < nodes[start].edge_index.size(); i++) {
        if (!rev) {
            if (edges[nodes[start].edge_index[i]].first == start && !nodes[edges[nodes[start].edge_index[i]].second].detected) {
                nodes[edges[nodes[start].edge_index[i]].second].leader = lead;
                DFS(edges[nodes[start].edge_index[i]].second);
            }
        }
        else if (edges[nodes[start].edge_index[i]].second == start && !nodes[edges[nodes[start].edge_index[i]].first].detected)
            DFS(edges[nodes[start].edge_index[i]].first);
    }
    if (rev)
        finish_time[count_t++] = start;
    c--;
}
bool comp(int a, int b) {
    return a > b;
}
void DFS_loop() {
    for (auto&& i : nodes)
        i.detected = false;
    count_t = 0;
    //lli extra[10000];
    finish_time.resize(nodes.size() - 1);
    for (int i = 1; i < nodes.size(); i++) {
        if (!nodes[i].detected) {
            lead = i;
            rev = true;
            DFS(i);
        }
    }
    for (auto&& i : nodes)
        i.detected = false;
    rev = false;
    for (int i = (signed int)finish_time.size() - 1; i >= 0; i--) {
        if (!nodes[finish_time[i]].detected) {
            nodes[finish_time[i]].leader = finish_time[i];
            lead = finish_time[i];
            DFS(finish_time[i]);
        }
    }
    for (int i = 1; i < nodes.size(); i++)
        SCC[nodes[i].leader].push_back(i);
    map<int, vector<int>>::iterator itr;
    for (itr = SCC.begin(); itr != SCC.end(); itr++) {
        SCC_size.push_back(itr->second.size());
    }
}
int main() {
    ifstream file;
    file.open("SCC.txt");
    file.seekg(0);
    if (file.is_open()) {
        while (true) {
            int temp, temp1;
            file >> temp >> temp1;
            if (!file)
                break;
            if (nodes.size() <= max(temp, temp1))
                nodes.resize((int)max(temp, temp1) + 1);
            edges.emplace_back(temp, temp1);
            nodes[temp].edge_index.push_back(edges.size() - 1);
            nodes[temp1].edge_index.push_back(edges.size() - 1);
        }
    }
    else {
        cout << "ERROR OPENING FILE";
        return -1;
    }
    file.clear();
    cout << "File Storing finished\n";
    DFS_loop();
    sort(SCC_size.begin(), SCC_size.end(), comp);
    for (int i = 0; i < 5 && i < SCC_size.size(); i++)
        cout << SCC_size[i] << " ";
    cout << endl;
    map<int, vector<int>>::iterator itr;
    /*for(itr = SCC.begin(); itr != SCC.end(); itr++){
        cout << itr->first << ": ";
        for(int i : itr->second)
            cout << i << " ";
        cout << endl;
    }*/
}

and here is exception: Unhandled exception at 0x00311287 in SCC.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x00602FE0).

Please don't apply tags who's description you didn't read. In this case, the "c" tag is completely wrong. Concerning your code, please transform it to something that anyone can just compile and run, i.e. a [mcve]. In particular the dependency on another file with the graph is bad. As a new user, please also take the [tour] and read [ask]. — Ulrich Eckhardt, Feb 02 '20 at 08:07
I know for the fact that recursion is not infinite since, if I use short int instead of int in edge, it executes without any exception but since many inputs are out of range of short int and unsigned short int range, it returns wrong answer — Vishnubly, Feb 03 '20 at 14:00
I am sorry for the bad question and I will make sure to not repeat these mistakes again and also try my best to create a minimal and reproducible example. — Vishnubly, Feb 03 '20 at 14:05

score 0 · Answer 1 · answered Feb 02 '20 at 08:15

The exception clearly states the reason - Stack Overflow.

The recursive DFS routine in your code is probably being called enough times to be exceeding the available stack size(or could be infinite as suggested by @Ulrich).

A few suggestions to handle this can be found here(How to handle or avoid a stack overflow in C++), but the general advice for such a problem is to switch to an iterative solution(eg. DFS using a std::stack).

Implementing DFS, works fine with shorter inputs but, throw segmentation error with larger inputs

1 Answers1