Cod sursa(job #2708882)

Utilizator dolhasca001Birleanu Matei dolhasca001 Data 19 februarie 2021 15:48:23
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
vector <int> lista[100001];
struct ura
{
    int nod,l;
}coada[100001];
int n,viz[100001];
int main()
{
    int s,maxi=0,p,x,y,prim,ultim,i;
    in>>n;
    while(in>>x>>y)
    {
        lista[x].push_back(y);
        lista[y].push_back(x);
    }
    coada[1].nod=1;
    viz[1]=1;
    coada[1].l=0;
    prim=ultim=1;
    while(prim<=ultim)
    {
        s=coada[prim].nod;
        for(i=0;i<=lista[s].size()-1;i++)
            {
                if(viz[lista[s][i]]==0)
                {
                  ultim++;
                  coada[ultim].nod=lista[s][i];
                  coada[ultim].l=coada[prim].l+1;
                  viz[lista[s][i]]=1;
                  if(coada[ultim].l>maxi)
                  {
                      maxi=coada[ultim].l;
                      p=lista[s][i];
                  }
                }

            }
          prim++;


    }

    for(i=1;i<=n;i++)
    {
        coada[i].l=0;
        coada[i].nod=0;
    }
    for(i=1;i<=n;i++)
        viz[i]=0;
    viz[p]=1;
    prim=ultim=1;
    coada[1].nod=p;
    coada[1].l=0;
    maxi=0;
    while(prim<=ultim)
    {
        s=coada[prim].nod;
        for(i=0;i<=lista[s].size()-1;i++)
            {
                if(viz[lista[s][i]]==0)
                {
                  ultim++;
                  coada[ultim].nod=lista[s][i];
                  coada[ultim].l=coada[prim].l+1;
                  viz[lista[s][i]]=1;
                  if(coada[ultim].l>maxi)
                    maxi=coada[ultim].l;

                }

            }
          prim++;
}
    out<<maxi+1;


    return 0;
}