Cod sursa(job #2567032)

Utilizator AnduRazvanMindrescu Andu AnduRazvan Data 3 martie 2020 14:37:09
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 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;
}