Sunday, September 6, 2009

10301 - Rings and Glue - UVA

graph search algorithm, Depth First Search ( DFS ) or BFS  +  GEOMETRY

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