Cod sursa(job #1362486)

Utilizator Athena99Anghel Anca Athena99 Data 26 februarie 2015 12:57:17
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int inf= 1<<30;
const int nmax= 100000;

int d[nmax+1];

vector <int> v[nmax+1];

int bfs( int root, int k ) {
    for ( int i= 1; i<=nmax; ++i ) d[i]= inf;
    d[root]= 1;

    int ans= 0;
    queue <int> q;
    for ( q.push(root); !q.empty(); q.pop() ) {
        int x= q.front();
        for ( vector <int>::iterator it= v[x].begin(); it!=v[x].end(); ++it ) {
            if ( d[*it]==inf ) {
                d[*it]= d[x]+1;
                q.push(*it);

                if ( d[*it]>d[ans] ) {
                    ans= *it;
                }
            }
        }
    }

    if ( k==0 ) return ans;
    return d[ans];
}

int main(  ) {
    int n;
    fin>>n;
    for ( int i= 1; i<=n-1; ++i ) {
        int x, y;
        fin>>x>>y;

        v[x].push_back(y);
        v[y].push_back(x);
    }

    int aux, sol;
    aux= bfs(1, 0);
    sol= bfs(aux, 1);

    fout<<sol<<"\n";

    return 0;
}