Cod sursa(job #2220185)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 10 iulie 2018 20:44:53
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <vector>
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin ("darb.in");
ofstream fout ("darb.out");

using VI = vector < int >;
using VVI = vector < VI >;

const int Dim = 100001;
int Viz[Dim],D[Dim],ma,n;
VVI G;

void Dfs(int x);

int main() {

	fin >> n;
	G = VVI(n+1);
	int x,y;
	for (int  i = 1; i < n; ++i) {
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	D[1] = 1;
	Dfs(1);
	int poz;
	for ( int i = 1; i <= n; ++i)
		if ( D[i] > ma) {
			ma = D[i];
			poz = i;
		}
	memset(D,0,sizeof(D));
	memset(Viz,0,sizeof(Viz));
	Dfs(poz);
	ma = 0;
	for ( int i = 1; i <= n; ++i)
		ma = max(ma, D[i]);
	fout << ma+1;
}

void Dfs(int x) {

	Viz[x] = true;
	for ( const int & y : G[x] )
		if ( !Viz[y] ) {
			D[y] = D[x] + 1;
			Dfs(y);
		}
}