  An alternating graph is a directed graph whose vertex set is partitioned into
two classes, existential and universal. This forms the basic arena for a
plethora of infinite duration two-player games where Player~$\square$
and~$\ocircle$ alternate in a turn-based sliding of a pebble along the arcs
they control. We study alternating strongly-connectedness as a generalization
of strongly-connectedness in directed graphs, aiming at providing a linear time
decomposition and a sound structural graph characterization. For this a refined
notion of alternating reachability is introduced: Player~$\square$ attempts to
reach vertices without leaving a prescribed subset of the vertices, while
Player~$\ocircle$ works against. This is named \emph{safe alternating
reachability}. It is shown that every arena uniquely decomposes into safe
alternating strongly-connected components where Player~$\square$ can visit each
vertex within a given component infinitely often, without having to ever leave
out the component itself. Our main result is a linear time algorithm for
computing this alternating graph decomposition. Both the underlying graph
structures and the algorithm generalize the classical decomposition of a
directed graph into strongly-connected components. The algorithm builds on a
linear time generalization of the depth-first search on alternation, taking
inspiration from Tarjan 1972 machinery. Our theory has direct applications in
solving well-known infinite duration pebble games faster. Dinneen and
Khoussainov showed in 1999 that deciding a given Update Game costs $O(mn)$
time, where $n$ is the number of vertices and $m$ is that of arcs. We solve the
task in $\Theta(m+n)$ linear~time. The complexity of Explicit
McNaughton-M\"uller Games also improves from cubic to quadratic.
