Segmentation Fault - unordered_map(tarjan's algorithm)

61 views Asked by At

I have implemented Tarjan's algorithm to find strongly connected component in a graph and getting Segmentation fault for some large input.

#include <iostream>
#include <sstream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <unordered_map>

using namespace std;

class Graph {
public:
    int n, m;
    unordered_map<int, unordered_set<int>> graph;

    Graph(int n, int m): n(n), m(m) {}

    void add_edge(int u, int v) {
        graph[u].insert(v);
        if(graph.find(v) == graph.end()) graph[v] = unordered_set<int>();
    }
    
    void scc_helper(int u, unordered_map<int, int>& disc,  unordered_map<int, int>& low, stack<int>& st, unordered_map<int, bool>& inStack, vector<unordered_set<int>>& scc, int& time) {
        disc[u] = low[u] = time++;
        st.push(u);
        inStack[u] = true;

        for(const int& ch: graph[u]) {
            if(disc[ch] == 0) {
                scc_helper(ch, disc, low, st, inStack, scc, time);
                low[u] = min(low[u], low[ch]);
            } else if(inStack[ch]) {
                low[u] = min(low[u], disc[ch]);
            }
        }
        if(disc[u] == low[u]) {
            scc.push_back(unordered_set<int>());
            while(st.top() != u) {
                scc.back().insert(st.top());
                inStack[st.top()] = false;
                st.pop();
            }
            scc.back().insert(st.top());
            inStack[st.top()] = false;
            st.pop();
        }
    };

    vector<unordered_set<int>> get_scc() {
        unordered_map<int, int> disc, low;
        stack<int> st;
        unordered_map<int, bool> inStack;
        vector<unordered_set<int>> scc;
        
        int time = 1;
        for(const auto& p: graph) {
            if(disc[p.first] == 0) 
                scc_helper(p.first, disc, low, st, inStack, scc, time);
        } 
        cerr << "completed" << endl;
        return scc;
    }
};

void read(string& input) {
    do {
        getline(cin, input);
    } while(input.length() > 0 && input[0] == '%');
}

Graph read_graph() {
    string input;
    istringstream ss;
    int n, m, v;

    read(input); ss.str(input);
    ss >> n >> m;
    ss.clear();

    Graph G(n, m);

    for(int u=1; u<=n; u++) {
        read(input); ss.str(input);
        while(ss >> v) {
            G.add_edge(u, v);
        } ss.clear();
        if(G.graph.find(u) == G.graph.end()) G.graph[u] = unordered_set<int>();
    }
    return G;
}

int main() {
    Graph G = read_graph();
    cerr << "read input\n";
    vector<unordered_set<int>> scc = G.get_scc();

    cout << scc.size() << "\n";
}

After debugging, I have found that the condition if(disc[u] == low[u]) is not getting evaluated to true when program throws segmentation fault. Another thing is that, Segmentation fault was received on lines disc[u] = low[u] = time++;, st.push(u); and inStack[u] = true; and at that time there were approx. 20,000 entries in each of the unordered_map and in stack.

Some details about input: for, n=16384 m=283794, the program is working correctly but for, n=58960 m=269439, it is throwing segmentation fault.

0

There are 0 answers