[Verse 1]
Graph algorithms on my mind, searching for the strongest ties
Components that are tightly bound, where every path can realize
A cycle back to where it started, that's the game we're playing here
Tarjan came up with the method, made the complex crystal clear
Stack it up and track the depth, discovery time on every node
Low-link values tell the story, as we walk the directed road
One traversal does it all, no need to run it twice
Strongly connected pieces fall, precision clean and nice
[Chorus]
Push it on the stack, track the low-link back
Discovery time climbing, never looking slack
When the root is found, pop until you're done
Tarjan's got the power, all components won
Stack and track, low-link back
One pass through, that's the hack
Stack and track, low-link back
Strongly connected, stay on track
[Verse 2]
DFS traversal is the base, but we enhance it with some flair
Discovery times increment, marking when we first get there
Low-link is the lowest numbered node that we can reach
Through descendants in our search, that's the lesson that we teach
When we finish with a node, check if it's a root you see
Discovery equals low-link value, that's the key identity
Pop the stack until we find it, that's a component right there
All the nodes between them binding, strongly connected pair
[Chorus]
Push it on the stack, track the low-link back
Discovery time climbing, never looking slack
When the root is found, pop until you're done
Tarjan's got the power, all components won
Stack and track, low-link back
One pass through, that's the hack
Stack and track, low-link back
Strongly connected, stay on track
[Bridge]
Linear time complexity, that's the beauty of the flow
Every edge and vertex touched, efficient as algorithms go
Back edges update low-links, forward edges we ignore
Cross edges to the stack nodes, that's what updates are for
[Chorus]
Push it on the stack, track the low-link back
Discovery time climbing, never looking slack
When the root is found, pop until you're done
Tarjan's got the power, all components won
Stack and track, low-link back
One pass through, that's the hack
Stack and track, low-link back
Strongly connected, stay on track
[Outro]
Tarjan solved it clean
One pass, stack machine
Strongly connected scenes
Algorithm supreme