I first construct adjacency matrix then use DFS to split each component and find the maximum.

d = distance between two centers of the rings

rPlusR = radius of ring 'a' + radius of ring 'b'

if( d <> max(R[a], R[b])

then adjMat[a][b] = adjMat[b][a] = true

After constructing the adjacency matrix I easily run DFS on the constructed graph, each time DFS is invoked we have a new component so I count the vertices that are being marked during this DFS call and compare to the maximum.

for(int i = 0; i <>

if( mark[i] == false )

{

vertices = 0;

DFS( i );

if( vertices <>

mx = vertices;

}

I made a mistake in the output.

Note that if maximum is equal to 1 you don't have to print 's' at the end of output.

( thanks Pouria for his hint )

## No comments:

## Post a Comment