Cod sursa(job #1222931)

Utilizator rangerChihai Mihai ranger Data 24 august 2014 19:07:06
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define nmax 100010

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

int n,i;
vector<int> g[nmax];
int d[nmax];

int bfs(int s)
{
    int i;
    for (i=1;i<=n;i++) d[i]=-1;
    d[s]=0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int v=q.front();
        q.pop();
        for  (i=0;i<g[v].size();++i)
        if (d[g[v][i]]==-1) {
            d[g[v][i]]=d[v]+1;
            q.push(g[v][i]);
        }
    }
    int Max,rs;
    for (i=1;i<=n;i++) if (d[i]>Max) Max=d[i],rs=i;
    return rs;
}


int main()
{
    cin>>n;
    for(i=1;i<=n-1;i++) {
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int x=bfs(1);
    x=bfs(x);
    cout<<d[x]+1;
}