Cod sursa(job #2145309)

Utilizator dragosh122Alexiuc Dragos dragosh122 Data 27 februarie 2018 11:43:36
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

struct graf
{
    int nod;
    graf *leg;
};
graf *gr[100001];
int n;
void add(int x,int y)
{
    graf *p=new graf;
    p->nod=y;
    p->leg=gr[x];
    gr[x]=p;
}

int coada[1000001],h[100001],nod2;
bool viz[100001];
void BFS()
{
    int inc=1,sf=1;
    coada[1]=1;
    int nc;
    int maxi=0;
    viz[1]=true;
    while(inc<=sf)
    {
        nc=coada[inc];
        for(graf *p=gr[nc];p;p=p->leg)
        {
            if(!viz[p->nod])
            {
                coada[++sf]=p->nod;
                viz[p->nod]=true;
                h[p->nod]=h[nc]+1;
                if(h[p->nod]>maxi)
                    maxi=h[p->nod],nod2=p->nod;
            }
        }
        inc++;
    }
}
int main()
{
    f>>n;
    int x,y;
    for(int i=1;i<n;i++)
    {
        f>>x>>y;
        add(x,y);
        add(y,x);
    }
    BFS();
    int inc=1,sf=1;
    int maxi=0;
    h[nod2]=1;
    int nc;
    coada[1]=nod2;
    viz[nod2]=false;
    while(inc<=sf)
    {
        nc=coada[inc];
        for(graf *p=gr[nc];p;p=p->leg)
        {
            if(viz[p->nod])
            {
                coada[++sf]=p->nod;
                viz[p->nod]=false;
                h[p->nod]=h[nc]+1;
                if(h[p->nod]>maxi)
                    maxi=h[p->nod];

            }
        }
        inc++;
    }
    g<<maxi;
    return 0;
}