Cod sursa(job #2570534)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 4 martie 2020 17:26:28
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define MAX 100010

using namespace std;

int n,x,y,ans,last;

int dp[MAX];
bool acc[MAX];
vector<int> nd[MAX];
queue<int> q;

void init(){
  for(int i=1;i<=n;i++)acc[i]=dp[i]=0;
}
void bfs(int start){
  acc[start]=1; q.push(start); dp[start]=1;
  while(!q.empty()){
    int ac=q.front(); q.pop();
    for(auto i:nd[ac])
      if(!acc[i]){
        acc[i]=1;
        dp[i]=dp[ac]+1;
        q.push(i);
      }
    last=ac;
    ans=dp[ac];
  }
}

int main()
{
    ifstream f ("darb.in");
    ofstream g ("darb.out");
    f>>n;
    for(int i=1;i<n;i++)
      f>>x>>y,
      nd[x].push_back(y),
      nd[y].push_back(x);
    bfs(1);
    init(); bfs(last);
    g<<ans<<'\n';
    f.close ();
    g.close ();
    return 0;
}