My Weblog

Blog about programming and math

SPOJ 9126. Time to live

SPOJ 9126. Time to live is almost similar to 1437. Longest path in a tree. Find the diameter of tree and maximal needed TTL for network will be radius of tree. Accepted c++ code.

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

vector<int> V[100100];
int vis[100100],dist[100100],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 , t;
          for(scanf("%d",&t) ;t > 0 ; t-- )
            {
		 scanf("%d",&n);
                 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].push_back(t2);
                         V[t2].push_back(t1);
                  }
		 
		 //if(n==2) { cout<<"1\n";continue;}

                 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);
		 int d = dist[n-1];
		 if( d & 1 ) cout<< ( d>>1 ) + 1 <<endl;
		 else cout<< ( d>>1 ) <<endl;
                 //cout<<dist[n-1]<<endl;

            }
 }
Advertisements

July 7, 2011 - Posted by | Programming | , , ,

2 Comments »

  1. Can you please give a little bit of proof of why this thing works?

    Comment by stan | February 19, 2015 | Reply

  2. nice solution. I learn a shorter way for Tree Diameter 🙂

    Comment by carl johnson | March 18, 2016 | 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: