Thursday 22 January 2015

(BFS APP 2) LONGEST   PATH  IN   A  TREE   BY  THE   USE    OF    ADJACENATARY     LIST.





#include<bits/stdc++.h>

using namespace std;
vector<int> vv[10001];

int lebel[10001];
int visited[10001];

void bfs(int src,int v)
{
    //cout<<v<<endl;
// cout<<"hi"<<endl;
 int i,rem;
 for(i=1;i<=v;i++) lebel[i]=-1;
 lebel[src]=0;

 for(i=1;i<=v;i++) visited[i]=0;  ///no vertex is visited yet

 visited[src]=1;

 queue<int> q;
 q.push(src);

 while(!q.empty())
 {
  rem=q.front();
  //cout<<"nikala"<<rem<<" ";
  q.pop();
  //cout<<vv[rem].size()<<" size ";
  for(i=0;i<vv[rem].size();i++)
  {

   if(visited[ vv[rem][i] ]!=1)
   {

     lebel[vv[rem][i]]=lebel[rem]+1;
    //      cout<<vv[rem][i]<<" "<<visited[ vv[rem][i] ]<<" "<<lebel[vv[rem][i]]<<endl;
     //cout<<vv[rem][i]<<" ";
     q.push(vv[rem][i]);
     visited[vv[rem][i]]=1;
   }
  }
 }

 /*cout<<"lebel" <<v<<endl;
for(int k=1;k<=v;k++)
    cout<<lebel[k]<<" ";
cout<<endl;*/

}

int main()
{
int i,j,p,q,rem,v;
cin>>v;

vector<pair<int ,int> > vec;

if(v==1)
{
    cout<<"0"<<endl;
    return 0;
}

for(i=1;i<v;i++)
{
     cin>>p>>q;
     vec.push_back(make_pair(p,q));
     vec.push_back(make_pair(q,p));
}

 for(i=1;i<=v;i++)
 {
   for(j=0;j<vec.size();j++)
   {
          if(vec[j].first==i)
          vv[i].push_back(vec[j].second);
   }
 }
//cout<<endl;
/*
 for(i=1;i<=v;i++)
 {
     for(j=0;j<vv[i].size();j++)

        cout<<vv[i][j]<<" ";
        //cout<<endl;
 }
*/
 bfs(1,v);

int max=0;
for(i=1;i<=v;i++)
{
 if(lebel[i]>max)
 {
  rem=i;
  max=lebel[i];
 }
}

bfs(rem,v);

max=0;
for(i=1;i<=v;i++)
{
 if(lebel[i]>max)
 {
  rem=i;
  max=lebel[i];
 }
}
cout<<max<<endl;

return 0;
}

No comments:

Post a Comment

Uploading and Running Lambda function in AWS

Main.go package main import ( "fmt" "encoding/json" "log" "github.com/aws/aws-lambda-g...