My Weblog

Blog about programming and math

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

September 16, 2010 - Posted by | Programming

2 Comments »

  1. could u post some test cases !!

    Comment by chinmay | June 4, 2011 | Reply

  2. Thanks man, this post helped!

    Comment by anirudh | December 24, 2012 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: