THIS PROBLEM NEEDS TO BE CODED IN JAVA BECAUSE THERE IS NO C++ SUPPORT FOR
MATRIX2D
Class name: Connected
Method name: largestComponent
Parameters: Matrix2D
Returns: int
An unweighted directed graph is set of v vertices (points), numbered 0 to
v-1, and e directed edges. A directed edge connects one vertex to another
vertex. Note if there is a directed edge from vertex m to n, there is not
necessarily a directed edge from vertex n to m, hence a directed graph.
An unweighted directed graph of v vertices can be represented as a v X v
matrix of 0s and 1s. The rows and columns of the matrix are numbered 0 to v-1,
(0,0) being the upper left element and (v-1,v-1) being the lower right element.
The element in the (m,n) position of the matrix is:
*1 if there is a directed edge from vertex m to n.
*0 if there is not a directed edge from vertex m to n.
A path exits from vertex m to vertex n if there is a series of directed
edges that can be traversed to get from m to n. For example, if there is an
edge from m to o, an edge from o to p, and an edge from p to n, there is path
from m to n: m->o->p->n. A strongly-connected component is defined as a group
of vertices in a directed graph such that each vertex in the component is
reachable from each other vertex in the component through a path (a series of
edges).
Create a class Connected, which includes a method largestComponent. This
method takes as a parameter a Matrix2D defining a directed graph and returns
the number of vertices in the graph's largest strongly-connected component.
The method signature is:
public int largestComponent(Matrix2D agraph);
*agraph is a square matrix (number of rows and columns are equal) consisting of
only the integers 0 or 1.
*agraph has minimum dimensions 1 x 1 and maximum dimensions 10 x 10.
Note:
*A single vertex with no eges to or from is is a strongly connected component
with 1 vertex.
*An edge or path from a vertex to itself is not necessary for the vertex to be
in a strongly connected component. Therefore, all elements in the matrix of
the form (n,n) do not affect the output.
Examples:
*If agraph=[[1 0 0 1][1 1 0 1][0 0 1 0][1 0 0 1]], the largest
strongly-connected component is vertex 0 and vertex 3, and the method should
return 2.
Matrix2D is a TopCoder developed class to represent a 2-dimensional matrix of
Objects. The matrix has r rows, numbered 0 to r-1, and c columns, numbered 0
to c-1.
To use Matrix2D, import tcclasses.Matrix2D.
The constructor takes two ints. The first is the number of rows in the matrix,
the second is the number of columns in the matrix. The constructor initializes
every element to "0".
The methods are:
void Matrix2D.set(int row,int col, Object element) sets the (row,col) spot in
the matrix to be element.
Object Matrix2D.get(int row, int col) returns an Object that is the element at
(row,col).
int Matrix2D.numRows() returns the number of rows in the matrix.
int Matrix2D.numCols() returns the number of columns in the matrix.
String Matrix2D.toString() returns a String representation of the matrix.
Object Matrix2D.clone() returns an Object that is a shallow copy of the matrix.