public class TarjanSCC extends java.lang.Object
This implementation uses Tarjan's 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
KosarajuSharirSCC
and GabowSCC
.
For additional documentation, see Section 4.2 of Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
TarjanSCC(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(java.lang.String[] args)
Unit tests the TarjanSCC data type.
|
boolean |
stronglyConnected(int v,
int w)
Are vertices v and w in the same strong component?
|
public TarjanSCC(Digraph G)
G
- the digraphpublic int count()
public boolean stronglyConnected(int v, int w)
v
- one vertexw
- the other vertexpublic int id(int v)
v
- the vertexpublic static void main(java.lang.String[] args)