Cod sursa(job #1529277)

Utilizator MayuriMayuri Mayuri Data 20 noiembrie 2015 18:14:50
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

vector <int> G[100005];
vector <int> viz;
queue <int> q;
int frunzaa;

int bfs(int u, int n) {
    int s, maxim = 0, nr;
    viz.assign(n + 1, 0);
    viz[u] = 1;
    while(!q.empty()) {
        q.pop();
    }
    q.push(u);
    while(!q.empty()) {
        s = q.front();
        nr = G[s].size();

        if(viz[s] > maxim) {
            maxim = viz[s];
            frunzaa = s;
        }

        for(int i = 0; i < nr; ++ i) {
            int v = G[s][i];
            if(viz[v] == 0) {
                viz[v] = viz[s] + 1;
                q.push(v);
            }
        }

        q.pop();
    }
    return maxim;
}

int main() {
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);

    int m, x, y, frunza;
    scanf("%d", &m);

    for(int i = 1; i < m; ++ i) {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }

    bfs(1, m);
    printf("%d", bfs(frunzaa, m));

    return 0;
}