Cod sursa(job #2425312)

Utilizator IordachescuAncaFMI Iordachescu Anca Mihaela IordachescuAnca Data 24 mai 2019 18:24:30
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

vector<vector<int>>G(100003);

void dfs(int source, vector<int> &viz, int lungime, int root)
{
	viz[source] = lungime;
	for(unsigned int i = 0; i < G[source].size(); i++)
	{
		if(!viz[G[source][i]] && G[source][i] != root)
		{
			dfs(G[source][i], viz, lungime+1, root);
		}
	}
}
int main()
{
	int n;
	fin >> n;
	for(int i = 0; i < n-1; i++)
	{
		int a, b;
		fin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	vector<int>viz(n+1, 0);
	dfs(1, viz, 0, 1);

	int vmax = viz[1];
	int ind = 1;
	for(int i = 1; i <= n; i++)
	{
		if(vmax < viz[i])
		{
			vmax = viz[i];
			ind = i;
		}
	}

	vector<int>viz1(n+1, 0);
	dfs(ind, viz1, 0, ind);

	vmax = viz1[1];
	for(int i = 1; i <= n; i++)
	{
		if(vmax < viz1[i])
		{
			vmax = viz1[i];
		}
	}

	fout << vmax+1;
	fin.close();
	fout.close();
	return 0;
}