Cod sursa(job #2578207)

Utilizator andra1782Andra Alazaroaie andra1782 Data 10 martie 2020 19:01:57
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <stdio.h>
#include <vector>
#include <queue>
#define MAX 100000
FILE *fin,*fout;
char viz[MAX+1];
std::vector<int>l[MAX+1];

struct dist{
  int y,d;
};

dist bfs(int x){
  std::queue<dist>q;
  dist f={x,1};
  q.push(f);
  while(!q.empty()){
    f=q.front();
    viz[f.y]=1;
    q.pop();
    for(auto i: l[f.y])
      if(!viz[i])
        q.push({i,f.d+1});
  }
  return f;
}

int main(){
  fin=fopen("darb.in","r");
  fout=fopen("darb.out","w");
  int n,i,x,y;

  fscanf(fin,"%d",&n);
  for(i=1; i<n; i++){
    fscanf(fin,"%d%d",&x,&y);
    l[x].push_back(y);
    l[y].push_back(x);
  }
  dist r=bfs(1);
  for(i=1; i<=n; i++)
    viz[i]=0;
  r=bfs(r.y);
  fprintf(fout,"%d\n",r.d);
  fclose(fin);
  fclose(fout);
  return 0;
}