Cod sursa(job #2386839)

Utilizator vlad_popaVlad Popa vlad_popa Data 23 martie 2019 18:55:09
Problema Diametrul unui arbore Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>


#define INF	(0x3f3f3f3f)


std::vector<std::vector<int> > listNb;


void execBFS(int node, std::vector<int>& d) 
{
	d[node] = 0;
	
	std::vector<int> que;
	que.push_back(node);
	for (int i = 0; i < que.size(); ++ i) {
		int curNode = que[i];
		for (auto nb : listNb[curNode]) {
			if (d[nb] > d[curNode] + 1) {
				d[nb] = d[curNode] + 1;
				que.push_back(nb);
			}
		}
	}
}

int main ()
{
	std::ifstream in("darb.in");
	
	int N;
	in >> N;
	
	listNb.resize(N+1);
	
	for (int i = 0; i < N-1; ++ i) {
		int x, y;
		in >> x >> y;
		listNb[y].push_back(x);
		listNb[x].push_back(y);
	}
	
	in.close();
	
	std::vector<int> d(N+1, INF);
	execBFS(1, d);
	auto result = std::max_element(d.begin() + 1, d.end());
	int maxNode = std::distance(d.begin()+1, result) + 1;
	
	d = std::vector<int>(N+1, INF);
	execBFS(maxNode, d);
	result = std::max_element(d.begin() + 1, d.end());
	
	std::ofstream out("darb.out");
	
	out << *result+1 << "\n";	
	
	out.close();
	
	return 0;
}