public class TarjanSCC extends Object
TarjanSCCclass represents a data type for determining the strong components in a digraph. The id operation determines in which strong component a given vertex lies; the areStronglyConnected operation determines whether two vertices are in the same strong component; and the count operation determines the number of strong components.
The component identifier of a component is one of the vertices in the strong component: two vertices have the same component identifier if and only if they are in the same strong component.
This implementation uses Tarjan's algorithm.
The constructor takes Θ(V + E) time,
where V is the number of vertices and E is the
number of edges.
Each instance method takes Θ(1) time.
It uses Θ(V) extra space (not including the digraph).
For alternative implementations of the same API, see
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
|Constructor and Description|
Computes the strong components of the digraph
|Modifier and Type||Method and Description|
Returns the number of strong components.
Returns the component id of the strong component containing vertex
Unit tests the
public TarjanSCC(Digraph G)
G- the digraph
public int count()
public boolean stronglyConnected(int v, int w)
win the same strong component?
public int id(int v)
v- the vertex
0 <= v < V
public static void main(String args)
args- the command-line arguments