publicTarjanSccSolverAdjacencyList(List<List<Integer>> graph) { if (graph == null) thrownewIllegalArgumentException("Graph cannot be null."); n = graph.size(); this.graph = graph; }
// Returns the number of strongly connected components in the graph. publicintsccCount() { if (!solved) solve(); return sccCount; }
// Get the connected components of this graph. If two indexes // have the same value then they're in the same SCC. publicint[] getSccs() { if (!solved) solve(); return sccs; }
for (int to : graph.get(at)) { if (ids[to] == UNVISITED) { dfs(to); } if (visited[to]) { low[at] = min(low[at], low[to]); } /* TODO(william): investigate whether the proper way to update the lowlinks is the following bit of code. From my experience this doesn't seem to matter if the output is placed in a separate output array, but this needs further investigation. if (ids[to] == UNVISITED) { dfs(to); low[at] = min(low[at], low[to]); } if (visited[to]) { low[at] = min(low[at], ids[to]); } */
}
// On recursive callback, if we're at the root node (start of SCC) // empty the seen stack until back to root. if (ids[at] == low[at]) { for (intnode= stack.pop(); ; node = stack.pop()) { visited[node] = false; sccs[node] = sccCount; if (node == at) break; } sccCount++; } }
// Initializes adjacency list with n nodes. publicstatic List<List<Integer>> createGraph(int n) { List<List<Integer>> graph = newArrayList<>(n); for (inti=0; i < n; i++) graph.add(newArrayList<>()); return graph; }
// Adds a directed edge from node 'from' to node 'to' publicstaticvoidaddEdge(List<List<Integer>> graph, int from, int to) { graph.get(from).add(to); }