Cod sursa(job #2200278)

Utilizator emiemiEmi Necula emiemi Data 30 aprilie 2018 21:05:56
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");

int n, maxi, last, d[100001];
vector<int> v[100001];

void bfs(int x) {
	int a, i, len;
	queue<int> q;
	q.push(x);
	d[x] = 1;
	while (!q.empty()) {
		a = q.front();
		q.pop();
		len = v[a].size();
		for(i = 0; i < len; ++i)
			if (!d[v[a][i]]) {
				d[v[a][i]] = d[a] + 1;
				if (d[v[a][i]] > maxi) {
					maxi = d[v[a][i]];
					last = v[a][i];
				}
				q.push(v[a][i]);
			}
	}
}

int main() {
	int i, x, y;
	f >> n;

	for (i = 1; i < n; ++i) {
		f >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}

	bfs(1);
	memset(d, 0, sizeof(d));
	bfs(last);
	g << maxi << '\n';


	return 0;
}