Cod sursa(job #1712833)

Utilizator serban_andreiserban andrei-catalin serban_andrei Data 3 iunie 2016 20:18:25
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>;
#define nmax 100014

using namespace std;

vector<int>arb[nmax];

queue<int>c;

int dist[nmax],n,x,y,aux,lungime,i,maxim=-999;

int main()
{
    ifstream f("darb.in");
    ofstream g("darb.out");
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>x>>y;
        arb[x].push_back(y);
        arb[y].push_back(x);


    }
    for(int i=2;i<=n;i++)
        dist[i]=1<<30;
    dist[1]=0;
    c.push(1);
    while(c.empty()==0)
    {
        int nod=c.front();
        c.pop();
        for(auto vecin:arb[nod])
        {
            if(dist[vecin]>dist[nod]+1)
            {
                dist[vecin]=dist[nod]+1;
                c.push(vecin);

            }

        }

    }

    for(i=1;i<=n;i++)
    {
        if(dist[i]>maxim)
        {
            maxim=dist[i];
            aux=i;

        }
    }
    for(i=1;i<=n;i++)
        dist[i]=1<<30;
    lungime=dist[aux];
    dist[aux]=1;
    c.push(aux);
    while(c.empty()==0)
    {
        int nod=c.front();
        c.pop();
        for(auto x:arb[nod])
        {
          if(dist[x]>dist[nod]+1)
            {
                dist[x]=dist[nod]+1;
                c.push(x);

            }
        }
    }
    for(i=1;i<=n;i++)
    {
        if(dist[i]>maxim)
        {
            maxim=dist[i];
            lungime=dist[i];
        }
    }
    g<<lungime;
    return 0;
}