Cod sursa(job #2091977)

Utilizator PaulTPaul Tirlisan PaulT Data 20 decembrie 2017 18:48:07
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
/* Se da un arbore si Q query-uri de tipul x y
 * Pt fiecare query. sa se det daca x y se afla in relatia ascendent/descendent
 */ 

#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

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

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

VVI G;     
VB viz;   
int n, m, dmax, node;
int root = 1;

void ReadGraph();
void Df(int x, int d);
int main()
{
	ReadGraph();
	Df(root, 0);
	dmax = 0;
	viz = VB(n + 1);
	Df(node, 0);
	fout << dmax + 1;
}


void ReadGraph()
{
	int x, y;
	fin >> n;
	G = VVI(n + 1);
	viz = VB(n + 1);
	for (int i = 1; i < n; ++i)
	{
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
		
}

void Df(int x, int d)
{
	viz[x] = 1;
	if (d > dmax)
		dmax = d, node = x;
		
	for (int i = 0; i < G[x].size(); ++i)
		if(!viz[G[x][i]])
			Df(G[x][i], d + 1);
}