Pagini recente » Cod sursa (job #463316) | Cod sursa (job #2460805) | Cod sursa (job #380375) | Cod sursa (job #2426621) | Cod sursa (job #2469661)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int const maxim = 100000;
int distanta[maxim];
int n;
int maxim1 = 0, maxim2 = 0;
int nod1 = 0, nod2 = 0;
vector <int> stocare[maxim];
queue <int> coada;
bool okay = true;
void citire() {
ifstream in("darb.in");
in >> n;
for (int i = 1; i <= n; i++) {
int a, b;
in >> a >> b;
stocare[a].push_back(b);
stocare[b].push_back(a);
}
in.close();
}
void bfs() {
int nod, vecin;
while (!coada.empty()) {
nod = coada.front();
coada.pop();
for (size_t i = 0; i < stocare[nod].size(); i++) {
vecin = stocare[nod][i];
if (distanta[vecin] == -1) {
distanta[vecin] = distanta[nod] + 1;
if (okay) {
if (distanta[vecin] > maxim1) {
maxim1 = distanta[vecin];
nod1 = vecin;
}
}
else {
if (distanta[vecin] > maxim2) {
maxim2 = distanta[vecin];
nod2 = vecin;
}
}
coada.push(vecin);
}
}
}
}
void diametru() {
for (int i = 1; i <= n; i++) {
distanta[i] = -1;
}
distanta[1] = 1;
coada.push(1);
bfs();
okay = false;
for (int i = 1; i <= n; i++) {
distanta[i] = -1;
}
distanta[nod1] = 1;
coada.push(nod1);
bfs();
ofstream out("darb");
out << maxim2;
out.close();
}
int main()
{
citire();
diametru();
return 0;
}