Pagini recente » Cod sursa (job #2250419) | Cod sursa (job #1421756) | Cod sursa (job #2158352) | Cod sursa (job #137639) | Cod sursa (job #2708825)
#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;
}