Cod sursa(job #1546831)

Utilizator RathebaSerbanescu Andrei Victor Ratheba Data 8 decembrie 2015 19:31:17
Problema Diametrul unui arbore Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 100002;

vector<int> v[MAX];
queue<int> q;
int n, dist[MAX];

void bfs(int source);

int main()
{
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    int a, b, imax=1;
    scanf("%d", &n);
    for(int i=1; i<n; i++)
    {
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    bfs(1);
    for(int i=1; i<=n; i++)
    {
        if(dist[imax] < dist[i])
            imax = i;
        dist[i] = 0;
    }
    bfs(imax);
    imax = 1;
    for(int i=2; i<=n; i++)
        if(dist[imax] < dist[i])
            imax = i;
    printf("%d\n", dist[imax]);
    return 0;
}
void bfs(int source)
{
    int tata, fiu;
    vector<int>::iterator it;

    while(!q.empty()) q.pop();
    dist[source] = 1;

    q.push(source);
    while(!q.empty())
    {
        tata = q.front();
        q.pop();
        for(it=v[tata].begin(); it!=v[tata].end(); ++it)
        {
            fiu = *it;
            if(!dist[fiu]) {
                dist[fiu] = dist[tata] + 1;
                q.push(fiu);
            }
        }
    }
}