Package edu.princeton.cs.algs4
Class CC
 Object

 edu.princeton.cs.algs4.CC

public class CC extends Object
TheCC
class represents a data type for determining the connected components in an undirected graph. The id operation determines in which connected component a given vertex lies; the connected operation determines whether two vertices are in the same connected component; the count operation determines the number of connected components; and the size operation determines the number of vertices in the connect component containing a given vertex. The component identifier of a connected component is one of the vertices in the connected component: two vertices have the same component identifier if and only if they are in the same connected component.This implementation uses depthfirst search. 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 graph).
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Constructor Summary
Constructors Constructor Description CC(EdgeWeightedGraph G)
Computes the connected components of the edgeweighted graphG
.CC(Graph G)
Computes the connected components of the undirected graphG
.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
connected(int v, int w)
Returns true if verticesv
andw
are in the same connected component.int
count()
Returns the number of connected components in the graphG
.int
id(int v)
Returns the component id of the connected component containing vertexv
.static void
main(String[] args)
Unit tests theCC
data type.int
size(int v)
Returns the number of vertices in the connected component containing vertexv
.



Constructor Detail

CC
public CC(Graph G)
Computes the connected components of the undirected graphG
. Parameters:
G
 the undirected graph

CC
public CC(EdgeWeightedGraph G)
Computes the connected components of the edgeweighted graphG
. Parameters:
G
 the edgeweighted graph


Method Detail

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

size
public int size(int v)
Returns the number of vertices in the connected component containing vertexv
. Parameters:
v
 the vertex Returns:
 the number of vertices in the connected component containing vertex
v
 Throws:
IllegalArgumentException
 unless0 <= v < V

count
public int count()
Returns the number of connected components in the graphG
. Returns:
 the number of connected components in the graph
G

connected
public boolean connected(int v, int w)
Returns true if verticesv
andw
are in the same connected component. Parameters:
v
 one vertexw
 the other vertex Returns:
true
if verticesv
andw
are in the same connected component;false
otherwise Throws:
IllegalArgumentException
 unless0 <= v < V
IllegalArgumentException
 unless0 <= w < V

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

