## Spoj Longest path in a tree

This problem can be solved using 2 dfs. First you can chose any arbitrary node and run dfs and find out distance to all other node from this chosen node. Now the node which has the greatest distance , run dfs from this node and find out maximum distance.

#include<cstdio> #include<iostream> #include<vector> using namespace std; vector<int> V[10010]; int vis[10010],dist[10010],k; void dfs(int v,int n) { vis[v]=1; dist[v]=n; for(int u=0;u<V[v].size();u++) if(!vis[V[v][u]]) dfs(V[v][u],n+1); } int main() { int n,t1,t2; while(scanf("%d",&n)!=EOF) { for(int i=0;i<n;i++) V[i].clear(),vis[i]=0; for(int i=0;i<n-1;i++) { scanf("%d%d",&t1,&t2); V[t1-1].push_back(t2-1); V[t2-1].push_back(t1-1); } dist[0]=0; dfs(0,0); /* for(int i=0;i<n;i++) cout<<dist[i]<<" "; cout<<endl;*/ int node=0; for(int i=0;i<n;i++) if(dist[i]>dist[node]) node=i; memset(vis,0,sizeof(vis)); // cout<<"node"<<node<<endl; dfs(node,0); /*for(int i=0;i<n;i++) cout<<dist[i]<<" "; cout<<endl;*/ sort(dist,dist+n); cout<<dist[n-1]<<endl; } }

Advertisements

could u post some test cases !!

Comment by chinmay | June 4, 2011 |

Thanks man, this post helped!

Comment by anirudh | December 24, 2012 |