Pagini recente » Cod sursa (job #114674) | cni_preoji | Cod sursa (job #1357270) | Cod sursa (job #232510) | Cod sursa (job #1476240)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n;
typedef struct nod {
int index;
int distanta;
} nod;
// pornind de la sursa prin vectorii de vecini rulez bfs
nod* bfs(vector<nod*>* vecini, nod* sursa, int* maxDistance) {
bool* visited = new bool[n];
for (int i = 0; i < n; i++) {
visited[i] = false;
}
nod* last = sursa;
queue<nod*> q;
q.push(sursa);
visited[sursa->index] = true;
while(!q.empty()) {
nod* current = q.front();
q.pop();
for (int j = 0; j < vecini[current->index].size(); j++) {
nod* vecin = vecini[current->index][j];
if (!visited[vecin->index]) {
vecin->distanta = current->distanta + 1;
q.push(vecin);
visited[vecin->index] = true;
if (*maxDistance < vecin->distanta) {
*maxDistance = vecin->distanta;
last = vecin;
}
}
}
}
return last;
}
int main() {
freopen("darb.in", "r", stdin);
freopen ("darb.out","w",stdout);
scanf("%i", &n);
vector<nod*>* vecini = new vector<nod*>[n];
nod* sursa = NULL;
for (int i = 0; i < n - 1; i++) {
nod* u = new nod();
nod* v = new nod();
scanf("%i", &u->index);
u->index--;
u->distanta = -1;
scanf("%i", &v->index);
v->index--;
v->distanta = -1;
vecini[u->index].push_back(v);
vecini[v->index].push_back(u);
sursa = u;
}
int maxDistance = 0;
sursa->distanta = 0;
nod* x = bfs(vecini, sursa, &maxDistance);
x->distanta = 0;
nod* y = bfs(vecini, x, &maxDistance);
printf("%i", maxDistance + 1);
fclose(stdin);
fclose(stdout);
return 0;
}