How to find maximum length of the longest street in the city by using BFS
Problem link: https://www.spoj.com/problems/BENEFACT/
Input:
1
6
1 2 3
2 3 4
2 6 2
6 4 6
6 5 5
Output:
12
Explanation:
6+2+4=12
At first start bfs from 1 and find the longest city from 1
And again start with bfs from this longest city and find the longest length
So we need two bfs search.
1st Code:
///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("lld%lld",&a,&b)
#define sf3(a,b,c) scanf("lld%lld%lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("lld%lld",a,b)
#define pf3(a,b,c) printf("lld%lld%lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
vector<long>vec[50005],cost[50005];
long vis[50005];
long bfs(long source)
{
queue<long>q;
memset(vis,0,sizeof(vis));
long dist[50005]= {0},boroman=0,mx=0;
dist[source]=0;
vis[50005]=1;
q.push(source);
long i;
while(!q.empty())
{
long u=q.front();
if(mx<dist[u])
{
mx=dist[u];
boroman=u;
}
for(i=0; i<vec[u].size(); i++)
{
long v=vec[u][i];
if(vis[v]==0)
{
dist[v]=dist[u]+cost[u][i];
vis[v]=1;
q.push(v);
}
}
q.pop();
}
return boroman;
}
long bfss(long source)
{
memset(vis,0,sizeof(vis));
queue<long>q;
long dist[50005]= {0},i,mx=0;
q.push(source);
vis[source]=1;
dist[source]=0;
while(!q.empty())
{
long u=q.front();
vis[u]=1;
if(mx<dist[u])
{
mx=dist[u];
}
for(i=0; i<vec[u].size(); i++)
{
long v=vec[u][i];
if(vis[v]==0)
{
dist[v]=dist[u]+cost[u][i];
// mx=max(mx,dist[v]);
vis[v]=1;
q.push(v);
}
}
q.pop();
}
return mx;
}
main()
{
long ts;
cin>>ts;
while(ts--)
{
long n,u,v,d,i;
cin>>n;
for(i=1; i<n; i++)
{
cin>>u>>v>>d;
vec[u].push_back(v);
vec[v].push_back(u);
cost[u].push_back(d);
cost[v].push_back(d);
}
long boro=bfs(1);
cout<<bfss(boro)<<endl;
for(i=0; i<=50005; i++)
{
vec[i].clear();
cost[i].clear();
vis[i]=0;
}
}
}
2nd Code:
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<cctype>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
using namespace std;
#define pb push_back
#define pi 3.141592653589793238462643383
int dist[50001];
int visited[50001];
int n;
struct node
{
int i,d;
};
typedef struct node node;
vector<node> v[50001];
int bfs(int start){
queue<int> q;
q.push(start);
int i,j;
for(i=0;i<=n;i++){
visited[i]=0;
dist[i]=0;
}
visited[start]=1;
while(!q.empty()){
int temp = q.front();
q.pop();
for(i=0;i<v[temp].size();i++){
if(visited[v[temp][i].i]==0){
visited[v[temp][i].i]=1;
dist[v[temp][i].i]+=dist[temp]+v[temp][i].d;
q.push(v[temp][i].i);
}
}
}
return int(max_element(dist+1,dist+n+1)-dist);
}
int main()
{
int i,j,t,u1,v1,d;
node temp;
scanf("%d",&t);
while(t>0){
scanf("%d",&n);
for(i=1;i<=n;i++)
v[i].clear();
for(i=1;i<=n-1;i++){
scanf("%d%d%d",&u1,&v1,&d);
temp.i = v1;
temp.d = d;
v[u1].pb(temp);
temp.i = u1;
v[v1].pb(temp);
}
int start = bfs(1);
cout<<start<<endl;
int ans = bfs(start);
printf("%d\n",dist[ans]);
t--;
}
}
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন