Cod sursa(job #2983212)

Utilizator mati.coldea@gmail.comMatei Coldea [email protected] Data 21 februarie 2023 20:15:53
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

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

vector<int> G[100005];
vector<int> d(100005);
void bfs(int k) {
	queue<int> Q;
	vector<int> viz(100005);
	Q.push(k);
	viz[k] = 1;
	d[k] = 1;
	while (!Q.empty()) {
		int act = Q.front();
		Q.pop();
		for (auto i : G[act]) {
			if (viz[i] == 0) {
				Q.push(i);
				viz[i] = 1;
				d[i] = d[act] + 1;
			}
		}

	}
}

int main() {

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


	bfs(1);
	int maxi = -1;
	int start=1;
	for (int i = 1; i <= n; i++) {
		//cout << d[i]<<' ';
		if (maxi < d[i]) {
			maxi = d[i];
			start = i;
		}
	}
	
	//cout << start << '\n';
	bfs(start);
	maxi = -1;
	for (int i = 1; i <= n; i++) {
		maxi = max(maxi, d[i]);
	}

	fout << maxi;
}