Cod sursa(job #1469131)

Utilizator SagunistuStrimbu Alexandru Sagunistu Data 7 august 2015 16:54:39
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define nmax 100005

using namespace std;

vector<int> g[nmax];
int n,s[nmax];

void citire()
{
    int x,y;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
}

void dfs(int k)
{
    for(vector<int>::iterator ii=g[k].begin();ii!=g[k].end();++ii)
        if(s[*ii]==0)
        {
            s[*ii]=s[k]+1;
            dfs(*ii);
        }
}

void maxim(int &mxm,int &pzmxm)
{
    for(int i=1;i<=n;i++)
            if(s[i]>mxm)
            {
                mxm=s[i];
                pzmxm=i;
            }
}

void rezolv()
{
    dfs(1);
    s[1]=1;
    int mxm=-1,pzmxm;
    maxim(mxm,pzmxm);
    memset(s,0,sizeof(s));
    s[pzmxm]=1;
    dfs(pzmxm);
    maxim(mxm,pzmxm);
    printf("%d\n",mxm);
}

int main()
{
    freopen("darb.in","r",stdin);
    freopen("darb.out","w",stdout);
    citire();
    rezolv();
    return 0;
}