Package edu.princeton.cs.algs4
Class TarjanSCC
 Object

 edu.princeton.cs.algs4.TarjanSCC

public class TarjanSCC extends Object
TheTarjanSCC
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 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
KosarajuSharirSCC
andGabowSCC
.For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description int
count()
Returns the number of strong components.int
id(int v)
Returns the component id of the strong component containing vertexv
.static void
main(String[] args)
Unit tests theTarjanSCC
data type.boolean
stronglyConnected(int v, int w)
Are verticesv
andw
in the same strong component?



Constructor Detail

TarjanSCC
public TarjanSCC(Digraph G)
Computes the strong components of the digraphG
. Parameters:
G
 the digraph


Method Detail

count
public int count()
Returns the number of strong components. Returns:
 the number of strong components

stronglyConnected
public boolean stronglyConnected(int v, int w)
Are verticesv
andw
in the same strong component? Parameters:
v
 one vertexw
 the other vertex Returns:
true
if verticesv
andw
are in the same strong component, andfalse
otherwise Throws:
IllegalArgumentException
 unless0 <= v < V
IllegalArgumentException
 unless0 <= w < V

id
public int id(int v)
Returns the component id of the strong component containing vertexv
. Parameters:
v
 the vertex Returns:
 the component id of the strong component containing vertex
v
 Throws:
IllegalArgumentException
 unless0 <= v < V

main
public static void main(String[] args)
Unit tests theTarjanSCC
data type. Parameters:
args
 the commandline arguments

