Cod sursa(job #3363260)

Utilizator horia.boeriuBoeriu Horia Andrei horia.boeriu Data 14 august 2026 17:51:01
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 100000;
const int NIL = 0;
int deq[MAXN], fr[MAXN + 1], pr[MAXN + 1];
int nrm, n;
struct cell {
    int x, nextp;
} vm[2 * MAXN];
void adaugMuchie(int x, int y) {
    nrm++;
    vm[nrm].x = y;
    vm[nrm].nextp = pr[x];
    pr[x] = nrm;
}
int bfs(int nod) {//il returnez pe cel mai departat de nod
    int pri, ul, i, x;
    for (i = 1; i <= n; i++) {
        fr[i] = 0;
    }
    fr[nod] = 1;
    deq[0] = nod;
    pri = 0;
    ul = 1;
    while (pri != ul) {
        nod = deq[pri];
        i = pr[nod];
        while (i != NIL) {
            x = vm[i].x;
            if (fr[x] == 0) {
                fr[x] = fr[nod] + 1;
                deq[ul] = x;
                ul++;
            }
            i = vm[i].nextp;
        }
        pri++;
    }
    return deq[ul - 1];
}
int main()
{
    //fac cu rerooting, se poate si cu fixarea lca-ului
    FILE *fin, *fout;
    int x, y, i;
    fin = fopen("darb.in", "r");
    fscanf(fin, "%d", &n);
    for (i = 0; i < n - 1; i++) {
        fscanf(fin, "%d%d", &x, &y);
        adaugMuchie(x, y);
        adaugMuchie(y, x);
    }
    fclose(fin);
    x = bfs(1);
    y = bfs(x);
    fout = fopen("darb.out", "w");
    fprintf(fout, "%d\n", fr[y]);
    fclose(fout);
    return 0;
}