(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;
}
#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;
}
Comments
Post a Comment