Cod sursa(job #2147578)

Utilizator remus88Neatu Remus Mihai remus88 Data 28 februarie 2018 20:35:55
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <queue>
#define Nmax 100009

using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");

int n,x,y,v[Nmax],maxx,pos;
vector <int> G[Nmax];
queue <int> Q;

void BFS(int node) {

    v[node]=1;
    Q.push(node);

    while (!Q.empty()) {

        int aux=Q.front();
        Q.pop();

        for (auto x: G[aux])
            if (v[x]==0) {

                v[x]=v[aux]+1;
                Q.push(x);
            }

    }
}

void ReadInput() {

    f>>n;
    for (int i=1; i<=n; ++i) {

        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void Solve() {

    BFS(1);
    for (int i=1; i<=n; ++i) {

        if (v[i]>maxx) {

            maxx=v[i];
            pos=i;
        }
        v[i]=0;
    }

    BFS(pos);
    maxx=0;
    for (int i=1; i<=n; ++i)
        if (v[i]>maxx) maxx=v[i];

    g<<maxx<<'\n';
}

int main() {

    ReadInput();
    Solve();

    f.close(); g.close();
    return 0;
}