Cod sursa(job #1925639)

Utilizator Mstar_AngelComan Mara Stefania Mstar_Angel Data 13 martie 2017 15:16:19
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<stdio.h>
#include<vector>
#define N 100001
using namespace std;
vector <int> v[N];
bool viz[N];
int dist[N];
int stiv[N];
int pozmax, n;
void init (){
  int i;
  for (i=1;i<=n;i++)
    viz[i] = dist[i] = 0;
}

void bfs (int nods){
  int inc,sf,nod,i;
  inc = sf = 1;
  stiv[1] = nods;
  dist[nods] = 1;
  viz[nods] = 1;
  pozmax = nods;
  while (inc <= sf){
    nod = stiv[inc];
    for (i=0;i<v[nod].size();i++)
      if (viz[v[nod][i]] == 0){
        viz[v[nod][i]] = 1;
        dist[v[nod][i]] = dist[nod] + 1;
        pozmax = dist[pozmax] > dist[v[nod][i]] ? pozmax : v[nod][i];
        stiv [++sf] = v[nod][i];
      }
    inc ++;
  }
}

int main (){
  FILE *in,*out;
  in = fopen ("darb.in","r");
  out = fopen ("darb.out","w");
  int i,n1,n2;
  fscanf(in,"%d",&n);
  for (i=1;i<=n-1;i++){
    fscanf(in,"%d%d",&n1,&n2);
    v[n1].push_back(n2);
    v[n2].push_back(n1);
  }

  init();
  bfs (1);
  init();
  bfs(pozmax);
  fprintf (out,"%d",dist[pozmax]);

  fclose (in);
  fclose (out);
  return 0;
}