public class KosarajuSharirSCC extends Object
KosarajuSharirSCCclass 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 the Kosaraju-Sharir 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 KosarajuSharirSCC(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 <= s < V
public static void main(String args)
args- the command-line arguments