Cod sursa(job #1305420)

Utilizator danyro364Savu Ioan Daniel danyro364 Data 29 decembrie 2014 19:27:43
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <queue>
#include <cstdio>
#include <vector>
#define nmax 100001
#define pb push_back
using namespace std;
FILE *f=fopen("darb.in","r"),*g=fopen("darb.out","w");
queue <int> c;
vector <int> l[nmax];
int n,viz[nmax],lg[nmax],last;
void bf()
{
    int i,x,k;
    c.push(1);
    while(!c.empty())
    {
        k=c.front();
        c.pop();
        for(i=0;i<l[k].size();i++)
        {
            x=l[k][i];
            if(!viz[x])
            {
                c.push(x);
                last=x;
                viz[x]=1;
            }
        }
    }
}
int bfl()
{
    int i,x,k,diam=0;
    c.push(last);
    lg[last]=1;
    viz[last]=0;
    while(!c.empty())
    {
        k=c.front();
        c.pop();
        for(i=0;i<l[k].size();i++)
        {
            x=l[k][i];
            if(viz[x])
            {
                lg[x]=lg[k]+1;
                c.push(x);
                if(lg[x]>diam)
                diam=lg[x];
                viz[x]=0;
            }
        }
    }
    return diam;
}
int main()
{
    int i,j,m;
    fscanf(f,"%d",&n);
    for(i=1;i<n;i++)
    {
        int x,y;
        fscanf(f,"%d %d",&x,&y);
        l[x].pb(y);
        l[y].pb(x);
    }
    fclose(f);
    bf();
    fprintf(g,"%d",bfl());
    fclose(g);
    return 0;
}