package com.thealgorithms.datastructures.graphs;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* Java program that implements Tarjan's Algorithm to find Strongly Connected Components (SCCs) in a directed graph.
*
* <p>
* Tarjan's algorithm is a linear time algorithm (O(V + E)) that identifies the SCCs of a directed graph.
* An SCC is a maximal subgraph where every vertex is reachable from every other vertex within the subgraph.
*
* <h3>Algorithm Overview:</h3>
* <ul>
* <li>DFS Search: A depth-first search (DFS) is performed on the graph to generate a DFS tree.</li>
* <li>Identification of SCCs: SCCs correspond to subtrees within this DFS tree.</li>
* <li>Low-Link Values: For each node, a low-link value is maintained, which indicates the earliest visited
* vertex (the one with the minimum insertion time) that can be reached from that subtree.</li>
* <li>Stack Usage: Nodes are stored in a stack during DFS. When an SCC is identified, nodes are popped from
* the stack until the head of the SCC is reached.</li>
* </ul>
*
* <p>
* Example of a directed graph:
* <pre>
* 0 --------> 1 -------> 3 --------> 4
* ^ /
* | /
* | /
* | /
* | /
* | /
* | /
* | /
* | /
* | /
* V
* 2
* </pre>
*
* <p>
* For the above graph, the SCC list is as follows:
* <ul>
* <li>1, 2, 0</li>
* <li>3</li>
* <li>4</li>
* </ul>
* The order of nodes in an SCC does not matter as they form cycles.
*
* <h3>Comparison with Kosaraju's Algorithm:</h3>
* <p>
* Kosaraju's algorithm also identifies SCCs but does so using two DFS traversals.
* In contrast, Tarjan's algorithm achieves this in a single DFS traversal, leading to improved performance
* in terms of constant factors.
* </p>
*/
public class TarjansAlgorithm {
// Timer for tracking low time and insertion time
private int time;
// List to store all strongly connected components
private final List<List<Integer>> sccList = new ArrayList<>();
/**
* Finds and returns the strongly connected components (SCCs) of the directed graph.
*
* @param v the number of vertices in the graph
* @param graph the adjacency list representation of the graph
* @return a list of lists, where each inner list represents a strongly connected component
*/
public List<List<Integer>> stronglyConnectedComponents(int v, List<List<Integer>> graph) {
// Initialize arrays for insertion time and low-link values
int[] lowTime = new int[v];
int[] insertionTime = new int[v];
for (int i = 0; i < v; i++) {
insertionTime[i] = -1;
lowTime[i] = -1;
}
// Track if vertices are in the stack
boolean[] isInStack = new boolean[v];
// Stack to hold nodes during DFS
Stack<Integer> st = new Stack<>();
for (int i = 0; i < v; i++) {
if (insertionTime[i] == -1) {
stronglyConnCompsUtil(i, lowTime, insertionTime, isInStack, st, graph);
}
}
return sccList;
}
/**
* A utility function to perform DFS and find SCCs.
*
* @param u the current vertex being visited
* @param lowTime array to keep track of the low-link values
* @param insertionTime array to keep track of the insertion times
* @param isInStack boolean array indicating if a vertex is in the stack
* @param st the stack used for DFS
* @param graph the adjacency list representation of the graph
*/
private void stronglyConnCompsUtil(int u, int[] lowTime, int[] insertionTime, boolean[] isInStack, Stack<Integer> st, List<List<Integer>> graph) {
// Set insertion time and low-link value
insertionTime[u] = time;
lowTime[u] = time;
time++;
// Push current node onto the stack
isInStack[u] = true;
st.push(u);
// Explore adjacent vertices
for (Integer vertex : graph.get(u)) {
if (insertionTime[vertex] == -1) {
stronglyConnCompsUtil(vertex, lowTime, insertionTime, isInStack, st, graph);
// Update low-link value
lowTime[u] = Math.min(lowTime[u], lowTime[vertex]);
} else if (isInStack[vertex]) {
// Vertex is in the stack; update low-link value
lowTime[u] = Math.min(lowTime[u], insertionTime[vertex]);
}
}
// Check if the current vertex is the root of an SCC
if (lowTime[u] == insertionTime[u]) {
int w = -1;
List<Integer> scc = new ArrayList<>();
// Pop vertices from the stack until the root is found
while (w != u) {
w = st.pop();
scc.add(w);
isInStack[w] = false;
}
sccList.add(scc);
}
}
}