Cod sursa(job #2708825)

Utilizator Ana_22Ana Petcu Ana_22 Data 19 februarie 2021 14:51:53
Problema Diametrul unui arbore Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <stdio.h>
#include <vector>
#include <iostream>
#define NMAX 100000

using namespace std;

vector<int> lista[NMAX+1];
char viz[NMAX+1];
unsigned char coada[NMAX+1];
int d1[NMAX+1];
int sf, inc;

int main() {
    FILE *fin, *fout;
    int n, i, n1, n2, maxx, p, dist;
    fin = fopen( "darb.in", "r" );
    fscanf( fin, "%d", &n );
    for( i = 0; i < n - 1; i++ ) {
      fscanf( fin, "%d%d", &n1, &n2 );
      lista[n1].push_back( n2 );
      lista[n2].push_back( n1 );
    }
    fclose( fin );
    viz[1] = 1;
    sf = inc = 1;
    coada[inc] = 1;
    d1[1] = 1;
    while( inc <= sf ) {
      dist = d1[coada[inc]];
      for( i = 0; i < lista[coada[inc]].size(); i++ ) {
        if( viz[lista[coada[inc]][i]] == 0 ) {
          coada[++sf] = lista[coada[inc]][i];
          viz[lista[coada[inc]][i]] = 1;
          d1[lista[coada[inc]][i]] = dist + 1;
        }
      }
      inc++;
    }
    maxx = 0;
    for( i = 1; i <= n; i++ ) {
      if( d1[i] > maxx ) {
        maxx = d1[i];
        p = i;
      }
      d1[i] = viz[i] = 0;
    }
    viz[p] = 1;
    sf = inc = 1;
    coada[inc] = p;
    d1[p] = 1;
    while( inc <= sf ) {
      dist = d1[coada[inc]];
      for( i = 0; i < lista[coada[inc]].size(); i++ ) {
        if( viz[lista[coada[inc]][i]] == 0 ) {
          coada[++sf] = lista[coada[inc]][i];
          viz[lista[coada[inc]][i]] = 1;
          d1[lista[coada[inc]][i]] = dist + 1;
        }
      }
      inc++;
    }
    maxx = 0;
    for( i = 1; i <= n; i++ )
      if( d1[i] > maxx )
        maxx = d1[i];
    fout = fopen( "darb.out", "w" );
    fprintf( fout, "%d", maxx );
    fclose( fout );
    return 0;
}