Реализация DFS, отлично работает с более короткими входами, но выдает ошибку сегментации с большими входами

Question

Этот код, который я пишу, предназначен для обнаружения SCC в графе, это первое программируемое назначение «графов Стэнфорда и структур данных», но при больших входах он выдает ошибки исключения. Я пробовал это с различными IDE и все время получаю ошибку сегментации с большими входами. Мне бы очень хотелось выяснить проблему и как ее исправить, я хочу изменить свой подход, если это проблема. Я почти уверен, что это может быть связано с заполнением хранилища Dynami c. Вот код:

#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;
    }*/
}

и вот исключение: необработанное исключение в 0x00311287 в S CC .exe: 0xC00000FD: переполнение стека (параметры: 0x00000001, 0x00602FE0).

Answer 1

В исключении четко указана причина - Переполнение стека .

Рекурсивная подпрограмма DFS в вашем коде, вероятно, вызывается достаточно раз, чтобы превысить доступный размер стека (или может быть бесконечным, как предложено @Ulrich).

Здесь можно найти несколько предложений, чтобы справиться с этим ( Как обработать или избежать переполнения стека в C ++ ), но общие советы для такого проблема в том, чтобы переключиться на итеративное решение (например, DFS с использованием std :: stack ).