implementing Recursive DFS for Finding Strongly Connected Components in Java - Stack Overflow scenarios
I've searched everywhere and can't find a clear answer. I tried several approaches but none seem to work. I'm implementing Tarjan's algorithm to find strongly connected components (SCCs) in a directed graph using a recursive depth-first search (DFS) approach in Java. However, I'm working with a `StackOverflowError` when processing larger graphs, and I need to seem to identify why. My implementation is based on the standard algorithm, but I suspect there might be an scenario with how I'm managing the recursion or the data structures. Here's a simplified version of my code: ```java import java.util.*; public class TarjanSCC { private int index = 0; private Stack<Integer> stack = new Stack<>(); private boolean[] onStack; private int[] indices; private int[] lowLinks; private List<List<Integer>> components; private List<List<Integer>> graph; public TarjanSCC(List<List<Integer>> graph) { this.graph = graph; int n = graph.size(); onStack = new boolean[n]; indices = new int[n]; lowLinks = new int[n]; components = new ArrayList<>(); Arrays.fill(indices, -1); } public List<List<Integer>> findSCCs() { for (int v = 0; v < graph.size(); v++) { if (indices[v] == -1) { dfs(v); } } return components; } private void dfs(int v) { indices[v] = lowLinks[v] = index++; stack.push(v); onStack[v] = true; for (int w : graph.get(v)) { if (indices[w] == -1) { dfs(w); lowLinks[v] = Math.min(lowLinks[v], lowLinks[w]); } else if (onStack[w]) { lowLinks[v] = Math.min(lowLinks[v], indices[w]); } } if (lowLinks[v] == indices[v]) { List<Integer> component = new ArrayList<>(); int w; do { w = stack.pop(); onStack[w] = false; component.add(w); } while (w != v); components.add(component); } } } ``` This implementation works for smaller graphs, but when I test it on a graph with about 10,000 nodes and many edges, I hit a `StackOverflowError`. I suspect that my recursion depth is too high because of the structure of the graph. I've tried increasing the stack size with the `-Xss` option in the JVM (to `-Xss2m`), but it still fails. Is there a more iterative way I can implement this algorithm, or is there a way to optimize my current recursive implementation to avoid hitting the stack limit? Any suggestions would be greatly appreciated! My development environment is macOS. Any ideas what could be causing this? What am I doing wrong?