Delta Algorithmic Contest

I recently came up with two problems for a programming contest organized by Delta , the premier programming club in NIT Trichy (and the coolest thing that I am part of).

The contest link :
Delta Algorithmic Contest 

You can find both my problems here:

Count Bus Stops
Dependency


In this we will be discussing a solution to the first problem.

 A given set of locations are connected such that there is a unique path from each location to every other location. There are bus services from different places.
The problem is to find the maximum number of bus stops possible between any two locations.

The main idea here is to model the locations and roads as a tree with the locations as nodes and roads as edges. Since the roads are bi-directional one can model the problem efficiently using an undirected unweighted tree. The problem to find maximum number of bus stops then is essentially finding the diameter of tree.


The simplest way to do it is :-

1. Run BFS from any node to find the farthest leaf node. Label that node T.
2. Run another BFS to find the farthest node from T. Label it as U
3. The path you found in step 2 is the longest path in the tree and the diameter of the tree is dist between U and T.

The running time of the algorithm is same as running time of BFS. So the running time is O(N), where N is the number of nodes.