LOJ-1094: Farthest Nodes in a Tree
What The problem wants : The problems wants the 'maximum distance' between any two nodes of an undirected and weighted graph.
General approach to solution : The most brute force way (which will receive TLE) is to calculate the distance between all pair of nodes. This however is very inefficient .
A more efficient approach can be realized by taking two observations in concern. One the graph is a tree. This means the two nodes that are farthest from each other , at least one of them is the farthest node from the root node. Otherwise, a shorter path will exist between them via the root node. The furthest node can easily be found applying BFS with the root as source .
Now that we can find our first node we can simply find the farthest node from the first node using BFS with first node as source .
We can calculate the distance between each node from any one node by using an array & using the given weight of edges.
distance from source
= parent nodes distance from source
+ distance from parent node
.
The main algorithmic steps of solving this problem is given as below:
- Find the furthest node from the root node. Consider it the
first node
of the two farthest nodes.
- Calculate the distance of each node from the first node.
- Output highest distance calculated.
Notes : If you don't know about trees,graphs or BFS check the resources section .
Example Walkthrough : Lets see the above approach by going through the steps in case of given examples of the problem statement.
In the second test case, the graph is as below:
In this graph we will first use BFS on root/node-0 to find the furthest node from it. We can see the most distant node is node-4 with a distance of 50. So , node-4 will be one of the two furthest nodes or our first_node
. Now we will find the distance between the nodes from first_node
the same way as before.
We can see that the furthest node is node-1 with a distance of 80.
So, the answer will be 80.
Resources :
- Tree data structure (Wikipedia)
- Tree data structure visualization (YouTube)
- BFS by geek for geeks ( Blog )
- BFS by William Fiset (YouTube
- Total Graph Theory Basics (Youtube)
Code :
Here's an accepted code for the problem . The code is given in C++. This code also utilizes two STL in CPP Vector and Queue
If don't know about them check these links:
#include <bits/stdc++.h>
using namespace std;
bool vis[30000];
int distan[30000];
vector<int>Graph[30000];
vector<int>weight[30000];
void bfs(int a,int n);
void clr(int n);
int main()
{
int t,cas=0;
cin>>t;
while(t--)
{
int n,u,v,cost;
scanf("%d",&n);
for( int i = 0 ; i < n ; i++ )
{
Graph[i].clear();
weight[i].clear();
}
for( int i = 0; i < n-1 ; i++ )
{
scanf("%d %d %d",&u,&v,&cost);
Graph[u].push_back(v);
Graph[v].push_back(u);
weight[u].push_back(cost);
weight[v].push_back(cost);
}
int max_distance=-1,first_node;
clr(n);
bfs(0,n);
for(int i = 0; i < n; i++)
{
if(distan[i]>max_distance)
{
max_distance = distan[i];
first_node=i;
}
}
clr(n);
int ans=0;
bfs(first_node,n);
for(int i=0; i<n; i++)
{
if(distan[i]>ans)
{
ans = distan[i];
}
}
printf("Case %d: %d\n",++cas,ans);
}
return 0;
}
void bfs(int a,int n)
{
queue<int>q;
vis[a] = 1;
q.push(a);
while(!q.empty())
{
int top;
top = q.front();
q.pop();
for(int i=0; i<Graph[top].size(); i++)
{
int var = Graph[top][i];
if(!vis[var])
{
vis[var] = 1;
distan[var] = distan[top] + weight[top][i];
q.push(var);
}
}
}
}
void clr(int n)
{
for( int i = 0 ; i < n ; i++ )
{
vis[i] = 0;
distan[i] = 0;
}
}
Tutorial source