Cod sursa(job #1480333)

Utilizator blackoddAxinie Razvan blackodd Data 2 septembrie 2015 14:36:55
Problema Diametrul unui arbore Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;

ifstream is("darb.in");
ofstream os("darb.out");

#define MaxN 100001

int n, nod_max, dmax;
vector<int> G[MaxN], dist(MaxN);
bitset<MaxN> viz;

void Read();
void Dfs(int);
void Reset();

int main()
{
	Read();
	Dfs(1);
	Reset();
	Dfs(nod_max);
	os << dmax + 1;

	is.close();
	os.close();
    return 0;
}

void Reset()
{
	for (int i = 1; i <= n; ++i)
		dist[i] = 0;
	dmax = 0;
}

void Dfs(int i)
{
	viz[i] = true;

	for (const auto& p : G[i])
		if (!viz[p])
		{
			dist[p] = dist[i] + 1;
			if (dist[p] > dmax)
				dmax = dist[p];
			if (p > nod_max)
				nod_max = p;
			Dfs(p);
		}
			

	viz[i] = false;

}

void Read()
{
	is >> n;

	for (int i = 1, x, y; i < n; ++i)
	{
		is >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}

}