public class KosarajuSharirSCC extends Object
KosarajuSharirSCC
class 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 KosarajuSharir algorithm.
The constructor takes time proportional to V + E
(in the worst case),
where V is the number of vertices and E is the number of edges.
Afterwards, the id, count, and areStronglyConnected
operations take constant time.
For alternate implementations of the same API, see
TarjanSCC
and GabowSCC
.
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description 

KosarajuSharirSCC(Digraph G)
Computes the strong components of the digraph
G . 
Modifier and Type  Method and Description 

int 
count()
Returns the number of strong components.

int 
id(int v)
Returns the component id of the strong component containing vertex
v . 
static void 
main(String[] args)
Unit tests the
KosarajuSharirSCC data type. 
boolean 
stronglyConnected(int v,
int w)
Are vertices
v and w in the same strong component? 
public KosarajuSharirSCC(Digraph G)
G
.G
 the digraphpublic int count()
public boolean stronglyConnected(int v, int w)
v
and w
in the same strong component?v
 one vertexw
 the other vertextrue
if vertices v
and w
are in the same
strong component, and false
otherwiseIllegalArgumentException
 unless 0 <= v < V
IllegalArgumentException
 unless 0 <= w < V
public int id(int v)
v
.v
 the vertexv
IllegalArgumentException
 unless 0 <= s < V
public static void main(String[] args)
KosarajuSharirSCC
data type.args
 the commandline arguments