STACOUNT-Editorial

editorial
, ,
1

PROBLEM LINK:

PRACTICE
Editorialist: Yogesh Yogendra

DIFFICULTY:

MEDIUM

PREREQUISITES:

Graphs

PROBLEM:

IPL session is On. Cricket matches are being played in “N” different stadiums of India(stadium number is 0 based indexed).
All stadium are connected to each other, and distance between all the adjacent stadium are same i.e One.
The chef is currently in the Stadium number of 0.
As the chef is busy watching IPL so you have to find the stadium which is farthest from stadium 0 and also find that distance.
Note: If more than one stadiums are farthest from stadium 0 then print the stadium number which is minimum.

EXPLANATION:

Here simply you have to run BFS from Node 0, and keep on updating the distance till each Nodes.

SOLUTION:

#include<bits/stdc++.h>
#define int             long long int
#define pb              push_back
using namespace std;
 


int32_t main() {
    
    int n,e;
    cin>>n>>e;
    vector<int> g[n];
    for(int i=0;i<e;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    queue<int> q;
    q.push(0);
    vector<int> vis(n,0);
    while(!q.empty()){
        int val = q.front();
        q.pop();
        for(auto x:g[val]){
            if(!vis[x]){
                vis[x] = vis[val] + 1;
                q.push(x);
            }
        }
    }
    int stadium_number = -1;
    int dist = 0;
    for(int i=0;i<n;i++){
        if(vis[i]>dist){
            dist = vis[i];
            stadium_number = i;
        }
    }
    cout<<stadium_number<<" "<<dist;

    
    return 0;
}
1 Like