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.
Example-
Number of nodes=3
Number of edges=2
Edges-
1 2
2 3
Output-
2
(1->2->3 is the longest path in the given tree which has a length of 2 units).
Algorithm-
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.
Code-
#include<stdio.h> #include<vector> #include<algorithm> #include<iostream> using namespace std; vector<int>arr[10005]; int n,a,b,j=0,m; int color[10005],dist[10005]; //d denotes the distance of the node on which DFS is called from the starting vertex. void dfs(int node,int d) { color[node]=2; //marking the visited vertices dist[node]=d; for(int i=0;i<arr[node].size();++i) { if(color[arr[node][i]]==0) { dfs(arr[node][i],d+1); } } } int main() { int p; int i1; p=1;j=0; //n is the number of vertices scanf("%d",&n); for(i=0;i<n;i++) arr[i].clear(); for(i=0;i<n;++i) { color[i]=0;dist[i]=0; } //tree has n-1 edges while(j<n-1) { scanf("%d %d",&a,&b); //a and b denote the starting and ending vertices of an edge arr[a-1].push_back(b-1); arr[b-1].push_back(a-1); j++; } for(i=0;i<n;++i) { if(color[i]==0) dfs(i,0); } int max=0; // p denotes the vertex with maximum distance for(i=0;i<n;i++) { if(dist[i]>=max) { max=dist[i]; p=i; } } //resetting the arrays to call DFS again for(i=0;i<n;++i) { color[i]=0;dist[i]=0; } //calling dfs on vertex which has max distance dfs(p,0); max=0; for(i=0;i<n;i++) { if(dist[i]>=max) { max=dist[i]; p=i; } } cout<<max<<endl; return 0; }