KosarajuSharirSCC (Algorithms 4/e)

Object
- edu.princeton.cs.algs4.KosarajuSharirSCC

```
public class KosarajuSharirSCC
extends Object
```
The 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 vertex is an integer between 0 and k–1, where k is the number of strong components. 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 TarjanSCC and GabowSCC.
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors
Constructor Description

KosarajuSharirSCC(Digraph G)
Computes the strong components of the digraph G.

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 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?

Methods inherited from class java.lang.Object
clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - KosarajuSharirSCC
```
public KosarajuSharirSCC(Digraph G)
```
    Computes the strong components of the digraph G.
    
    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 vertices v and w in the same strong component?
    
    Parameters:
    
    v - one vertex
    
    w - the other vertex
    
    Returns:
    
    true if vertices v and w are in the same strong component, and false otherwise
    
    Throws:
    
    IllegalArgumentException - unless 0 <= v < V
    
    IllegalArgumentException - unless 0 <= w < V
  - id
```
public int id(int v)
```
    Returns the component id of the strong component containing vertex v.
    
    Parameters:
    
    v - the vertex
    
    Returns:
    
    the component id of the strong component containing vertex v
    
    Throws:
    
    IllegalArgumentException - unless 0 <= s < V
  - main
```
public static void main(String[] args)
```
    Unit tests the KosarajuSharirSCC data type.
    
    Parameters:
    
    args - the command-line arguments