Cod sursa(job #2030422)

Utilizator pSergiuPatras Sergiu pSergiu Data 1 octombrie 2017 16:51:33
Problema Diametrul unui arbore Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define NMAX 100001
int n,s;
ifstream fin("darb.in");
ofstream fout("darb.out");
int dist[NMAX];
queue <int> q;
vector <int> adiacenta[NMAX];

int maxDistance(){
    int i,mx=-1,poz;
    for(i=1;i<=n;i++)
            if(mx < dist[i]){
            mx = dist[i];
            poz = i;
    }

return poz;
}
void input(){
    int x,y,i;
    fin>>n;
    while(fin>>x>>y){
        adiacenta[x].push_back(y);
        adiacenta[y].push_back(x);
    }
}

void bfs(){
        for(int x;!q.empty();){
            x = q.front();
            q.pop();
            for(auto i: adiacenta[x])
            if(dist[i] == 0){
                q.push(i);
                dist[i] = dist[x]+1;
            }
        }
}

int main()
{
    input();
    dist[1] = 1;
    q.push(1);
    bfs();
    fill(dist,dist+n,0);
    q.push(maxDistance());
    dist[maxDistance()] = 1;
    bfs();
    int mx = -1;
    for(int i=1;i<=n;i++)
        mx = max(mx,dist[i]);
    fout<<mx;
    fin.close();
    fout.close();
    return 0;
}