Cod sursa(job #3195310)

Utilizator EftodeAndreiEftode Andrei EftodeAndrei Data 20 ianuarie 2024 14:01:58
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include<bits/stdc++.h>
using namespace std;
int n,a,maxk=INT_MIN;
vector<int>V[100001];
int t[1000001],t1[1000001];
bitset<100001>B,B1;
queue<int>q,q1;
ifstream in("darb.in");
ofstream out("darb.out");
int main() {
	in >> n;
	for (int i = 1; i < n; i++) {
		int x = 0, y = 0;
		in >> x >> y;
		V[x].push_back(y);
		V[y].push_back(x);
	}
	q.push(1);
	B[1] = 1;
	t[1] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (auto i : V[x]) 
			if (B[i] == 0) {
				B[i] = 1;
				q.push(i);
				t[i] = t[x] + 1;
				if (t[i] > maxk) maxk = t[i], a = i;
			}
	}
	B1[a] = 1;
	t1[a] = 1;
	q.push(a);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for(auto i:V[x])
			if (B1[i] == 0) {
				B1[i] = 1;
				t1[i] = t1[x] + 1;
				if (t1[i] > maxk) maxk = t1[i];
				q.push(i);
			}

	}
	out << maxk;
}