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