Given an unweighted and undirected tree,the task is to find the length of the longest path (from one node to another) in that tree.The length of a path in this case is number of edges we traverse from source to destination.
Number of nodes=3
Number of edges=2
(1->2->3 is the longest path in the given tree which has a length of 2 units).
1.Loop through the vertices, starting a new depth first search whenever the loop reaches a vertex that has not already been included in previous DFS calls.
2.A dist array is constructed to record the distances of all the vertices from the starting vertex ie. vertex on which DFS is called.
3.Maximum of all the values of the dist array is found and the respective vertex number is found.Let it be v.
4.Now,DFS is called on v and dist array records the distances of all the vertices from the vertex v.
5.Maximum of all the values of the dist array is the final answer that is it is the length of the longest path in the tree.
using namespace std;
//d denotes the distance of the node on which DFS is called from the starting vertex.
void dfs(int node,int d)
//marking the visited vertices
//n is the number of vertices
//tree has n-1 edges
//a and b denote the starting and ending vertices of an edge
// p denotes the vertex with maximum distance
//resetting the arrays to call DFS again
//calling dfs on vertex which has max distance