Cod sursa(job #1380217)

Utilizator DenisacheDenis Ehorovici Denisache Data 6 martie 2015 23:38:59
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n,last,diameter;
vector <int> G[100005];
bool used[100005];
#define pb push_back
void bfs(int nod)
{
    int Q[100005],cnt[100005];
    memset(cnt,0,sizeof(cnt));
    Q[0]=cnt[nod]=1; Q[1]=nod;
    for (int i=1;i<=Q[0];i++)
    {
        int x=Q[i];
        for (vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
        {
            if (!used[*it])
            {
                Q[++Q[0]]=*it;
                cnt[*it]=cnt[x]+1;
                used[*it]=true;
                if (cnt[*it]>diameter) diameter=cnt[*it];
            }
        }
    }
    if (!last) last=Q[Q[0]];
}
int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    scanf("%d",&n);
    int x,y;
    for (int i=1;i<n;i++)
    {
        scanf("%d %d",&x,&y);
        G[x].pb(y);
        G[y].pb(x);
    }
    bfs(1);
    memset(used,false,sizeof(used));
    bfs(last);
    printf("%d",diameter);
    return 0;
}