Cod sursa(job #1108280)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 15 februarie 2014 15:38:40
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

ifstream in ("darb.in");
ofstream out ("darb.out");

const int MAXN = 100010;

vector <int> Graf[MAXN];
queue <int> Q;
int Best[MAXN];
int Last, Dist;

void BFS (int S)
{
    Last = 0, Dist = 0;
    memset (Best, 0x3f, sizeof (Best));
    Best[S] = 0;
    Q.push (S);
    int nod;

    while (!Q.empty ()){
        nod = Q.front ();
        Q.pop ();

        for (auto it : Graf[nod])
            if (Best[nod] + 1 < Best[it]){
                Best[it] = Best[nod] + 1;
                Q.push (it);

                if (Best[it] > Dist)
                    Dist = Best[it], Last = it;
            }
        }
}

int main()
{
    int N, i, a, b;

    in >> N;
    for (i = 1; i < N; i ++){
        in >> a >> b;
        Graf[a].push_back (b);
        Graf[b].push_back (a);
    }

    BFS (1);
    BFS (Last);
    out << Dist + 1;

    return 0;
}