Sunday, October 17, 2010

924 - Spreading The News - UVA

graph search algorithm - BFS

In this problem you have to run BFS from a source, and find out that in the BFS-tree in which level you have the most nodes and in which level the most nodes come to BFS-tree.
I run BFS from the given source and find out the depth of each node from the source and then calculate which depth has the most nodes and what the level is.
if d[i] is the depth for node i from source then
for(int i = 0; i < n; i ++)
output[ d[i] ] ++;
find max from output and print the index of maximum as depth and output[index] as size of the maximum.
problem sample test case :
http://www.4shared.com/photo/va73oUQD/924_spreading_the_news.html

No comments:

Post a Comment

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...