Tarjan's algorithm finds all SCCs in a single DFS pass. It assigns each node a discovery time and a low-link value (smallest discovery time reachable via DFS tree + one back edge). When a node's low-link equals its discovery time, it is the root of an SCC, and all nodes above it on the stack form that SCC.
int timer=0;
void dfs(int v,vector<vector<int>>&g,vector<int>&disc,vector<int>&low,vector<bool>&onStack,stack<int>&st,vector<vector<int>>&sccs){
disc[v]=low[v]=timer++; st.push(v); onStack[v]=true;
for(int u:g[v]){
if(disc[u]==-1){dfs(u,g,disc,low,onStack,st,sccs);low[v]=min(low[v],low[u]);}
else if(onStack[u]) low[v]=min(low[v],disc[u]);
}
if(low[v]==disc[v]){
vector<int> scc;
while(true){int u=st.top();st.pop();onStack[u]=false;scc.push_back(u);if(u==v)break;}
sccs.push_back(scc);
}
}Each node gets a discovery time (disc) when first visited. The low-link (low) is the minimum discovery time reachable using DFS tree edges plus at most one back edge. If low[v]==disc[v], v is an SCC root.
Nodes are pushed onto a stack when visited and remain there until their SCC is complete. When an SCC root is found, pop all nodes down to and including the root — they form one SCC.
Tarjan's uses a single DFS pass vs Kosaraju's two passes. Both are O(V+E). Tarjan's is slightly more complex to implement but avoids building the transposed graph.
Quiz coming soon for this algorithm.