Cod sursa(job #2922211)

Utilizator PopaMihaimihai popa PopaMihai Data 6 septembrie 2022 10:22:44
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 1e5 + 3;

int N;
vector < int > G[NMAX];
int d[NMAX];

void BFS (int root)
{
	queue < int > q;
	q.push(root);
	sel[root] = true;	

	while(!q.empty()) {
		for(auto it: G[q.front()]) {
			if(!sel[it]) {
				q.push(it);
				sel[it] = true;
				d[it] = d[q.front()] + 1;
			}			
		}
		q.pop();
	}
}

void Solve()
{
	fin >> N;
	for(int i = 1; i < N; ++i) {
		int a, b;
		fin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	BFS(1);
	int far = 0;
	for(int i = 1; i <= N; ++i)
		if(d[far] < d[i])
			far = i;

	for(int i = 1; i <= N; ++i)
		d[i] = 0;

	BFS(far);
	
	int distmax = 0;
	for(int i = 1; i <= N; ++i)
		if(distmax < d[i])
			distmax = d[i];

	fout << distmax;
}

int main()
{
	Solve();
	return 0;
}