Cod sursa(job #2567765)

Utilizator MirunaStefaniaLupascu Miruna-Stefania MirunaStefania Data 3 martie 2020 18:46:07
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#define N 100005

using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

///aplicam dfs dintr un nod oarecare
///cel mai indepartat nod in care am ajuns stim sigur ca este frunza
///aplicam iar un dfs si acesta este cel mai lung lant posibil(diametru)

struct nod
{
    int info;
    nod* urm;
};

nod* g[N];
int n;
int viz[N];

int maxi, nextt;//pt frunza in care ajungem dupa primul dfs

void add(nod *&prim,int x)
{
    nod *p=new nod;
    p->info=x;
    p->urm=prim;
    prim=p;
}

void read()
{
    int i,x,y;
    fin>>n;
    for(i=1;i<=n-1;++i)
    {
        fin>>x>>y;
        add(g[x],y);
        add(g[y],x);
    }
}



void dfs(int x)
{
    int i;

    nod *p;
    for(p=g[x];p;p=p->urm)
        if(!viz[p->info])
            {
                viz[p->info]=viz[x]+1;
                if(viz[p->info]>maxi)
                {
                    maxi=viz[p->info];
                    nextt=p->info;
                }
                dfs(p->info);
            }
}


void solve()
{
    viz[1]=1;
    dfs(1);
    //cout<<next;
    for(int i=1;i<=n;++i)
        viz[i]=0;
    maxi=0;
    viz[nextt]=1;
    dfs(nextt);
    fout<<maxi;

}

int main()
{
    read();
    /*for(int i=1;i<=n;++i)
        {
        for(nod *p=g[i];p;p=p->urm)
            cout<<p->info<<" ";
        cout<<"\n";
        }*/

    solve();



    return 0;
}