Cod sursa(job #1196708)

Utilizator gbibBacotiu Gabi gbib Data 8 iunie 2014 22:54:06
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
int c[1000001],viz[1000001],cont[1000001];
vector <int> v[1000001];
int main()
{int u,p,i,n,x,m,a,b,j,d,last;
    in>>n;
    for(j=1;j<=n;j++)
        {
            in>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);

        }
    memset(cont,0,1000001);
    memset(viz,0,1000001);
    p=u=1;
    c[u]=1;
    cont[1]=1;
    viz[1]=1;
    while(u<=p)
    {
        for(i=0;i<v[c[u]].size();i++)
        {
            if(viz[v[c[u]][i]]==0)
            {
                cont[v[c[u]][i]]=cont[c[u]]+1;
                viz[v[c[u]][i]]=1;
                p++;
                d=cont[v[c[u]][i]];
                last=v[c[u]][i];
                c[p]=v[c[u]][i];
            }
        }
        u++;
    }

    memset(cont,0,1000001);
    memset(viz,0,1000001);
    p=u=1;
    c[u]=last;
    viz[last]=1;
    cont[last]=1;
    while(u<=p)
    {
        for(i=0;i<v[c[u]].size();i++)
        {
            if(!viz[v[c[u]][i]])
            {
                cont[v[c[u]][i]]=cont[c[u]]+1;
                viz[v[c[u]][i]]=1;
                p++;
                d=cont[v[c[u]][i]];
                last=v[c[u]][i];
                c[p]=v[c[u]][i];
            }
        }
        u++;
    }
out<<d<<'\n';
    in.close();
    out.close();
    return 0;
}