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.