Problem $7.$ Tarjan's algorithm is an efficient method for finding all strongly connected components $($SCCs$)$ of a directed graph $\backslash ($ G$=($V$,$ E$)\backslash )$ in linear time. A strongly connected component of a directed graph is a maximal subgraph in which any two vertices are reachable from each other. Tarjan's algorithm leverages Depth$-$First Search $($DFS$)$ to identify these components, ensuring each node in the graph is part of exactly one SCC$.$

The main idea of Tarjan's algorithm is to perform a DFS on $\backslash ($ G $\backslash ),$ keeping track of each vertex's discovery time $\backslash ($ v $\backslash ).$index $($a unique integer assigned in the order of discovery$)$ and a secondary value $\backslash ($ v $\backslash ).$lowlink, which is the smallest discovery index reachable from $\backslash ($ v $\backslash )$ in the DFS subtree, including $\backslash ($ v $\backslash )$ itself. The key steps of the algorithm are as follows:

$1.$ For each unvisited vertex $\backslash ($ v $\backslash )$ in $\backslash ($ G $\backslash ),$ initiate a DFS that assigns $\backslash ($ v $\backslash ).$index and $\backslash ($ v $\backslash ).$lowlink.

$2.$ Push each visited vertex onto a stack, and keep it on the stack until its strongly connected component has been fully explored.

$3.$ For each successor $\backslash ($ w $\backslash )$ of $\backslash ($ v $\backslash )$ :

$-$ If $\backslash ($ w $\backslash )$ has not yet been visited, recursively call the DFS on $\backslash ($ w $\backslash ).$ Update $\backslash ($ v $\backslash ).$lowlink as $\backslash (\backslash$min $($v $\backslash ).$lowlink, $\backslash ($ w $\backslash ).$lowlink$).$

$-$ If $\backslash ($ w $\backslash )$ is on the stack, update $\backslash ($ v $\backslash ).$lowlink as $\backslash (\backslash$min $($v $\backslash ).$lowlink, $\backslash ($ w $\backslash ).$index$).$

$4.$ After visiting all descendants of $\backslash ($ v $\backslash ),$ if $\backslash ($ v $\backslash ).$lowlink $\backslash (=$v $\backslash ).$index, then $\backslash ($ v $\backslash )$ is the root of a strongly connected component. Pop vertices from the stack until $\backslash ($ v $\backslash )$ is removed, forming one complete SCC$.$

Using the above description, prove the correctness of Tarjan's algorithm. In particular, demonstrate that:

$-$ The algorithm correctly identifies each strongly connected component.

$-$ Each vertex belongs to exactly one SCC$.$

$-$ The invariant properties of $\backslash ($ v $\backslash ).$index and $\backslash ($ v $\backslash ).$lowlink are maintained throughout the execution of the algorithm.