StronglyConnectedComponentOptimized.java

packagecom.thealgorithms.graph;

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Stack;

/**
 * Finds the strongly connected components in a directed graph.
 *
 * @param adjList The adjacency list representation of the graph.
 * @param n The number of nodes in the graph.
 * @return The number of strongly connected components.
 */
publicclassStronglyConnectedComponentOptimized {

publicvoidbtrack(HashMap<Integer, List<Integer>> adjList, int[] visited, Stack<Integer> dfsCallsNodes, intcurrentNode) {
visited[currentNode] = 1;
List<Integer> neighbors = adjList.get(currentNode);
// Check for null before iterating
if (neighbors != null) {
for (intneighbor : neighbors) {
if (visited[neighbor] == -1) {
btrack(adjList, visited, dfsCallsNodes, neighbor);
 }
 }
 }
dfsCallsNodes.add(currentNode);
 }

publicvoidbtrack2(HashMap<Integer, List<Integer>> adjRevList, int[] visited, intcurrentNode, List<Integer> newScc) {
visited[currentNode] = 1;
newScc.add(currentNode);
List<Integer> neighbors = adjRevList.get(currentNode);
// Check for null before iterating
if (neighbors != null) {
for (intneighbor : neighbors) {
if (visited[neighbor] == -1) {
btrack2(adjRevList, visited, neighbor, newScc);
 }
 }
 }
 }

publicintgetOutput(HashMap<Integer, List<Integer>> adjList, intn) {
int[] visited = newint[n];
Arrays.fill(visited, -1);
Stack<Integer> dfsCallsNodes = newStack<>();

for (inti = 0; i < n; i++) {
if (visited[i] == -1) {
btrack(adjList, visited, dfsCallsNodes, i);
 }
 }

HashMap<Integer, List<Integer>> adjRevList = newHashMap<>();
for (inti = 0; i < n; i++) {
adjRevList.put(i, newArrayList<>());
 }

for (inti = 0; i < n; i++) {
List<Integer> neighbors = adjList.get(i);
// Check for null before iterating
if (neighbors != null) {
for (intneighbor : neighbors) {
adjRevList.get(neighbor).add(i);
 }
 }
 }

Arrays.fill(visited, -1);
intstronglyConnectedComponents = 0;

while (!dfsCallsNodes.isEmpty()) {
intnode = dfsCallsNodes.pop();
if (visited[node] == -1) {
List<Integer> newScc = newArrayList<>();
btrack2(adjRevList, visited, node, newScc);
stronglyConnectedComponents++;
 }
 }

returnstronglyConnectedComponents;
 }
}