Cod sursa(job #2705838)

Utilizator DavidTosaDavid Tosa DavidTosa Data 13 februarie 2021 13:30:24
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
using namespace std;

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

struct nod{
    int info;
    nod* urm;
};
nod* v[100010];

int n,i,j,k,x,maxi;
int viz[100010],q[100010];

void muchie_noua(int x, int y)
{
    nod *r;

    r=new nod;
    r->urm=v[x];
    r->info=y;
    v[x]=r;

    r=new nod;
    r->urm=v[y];
    r->info=x;
    v[y]=r;
}

void BFS(int start)
{
    nod *r;
    int cs=1, ci=1, k;
    q[cs]=start;
    viz[start]=1;

    while(cs<=ci)
    {
        k=q[cs];
        cs++;
        r=v[k];
        while(r!=NULL)
        {
            if(viz[r->info]==0)
            {
                ci++;
                q[ci]=r->info;
                viz[r->info]=viz[k]+1;
                if(viz[r->info]>maxi)
                {
                    maxi=viz[r->info];
                    x=r->info;
                }
            }
            r=r->urm;
        }
    }
}

int main()
{
    fin>>n;
    while(fin>>i>>j)
        muchie_noua(i,j);

    BFS(i);
    for(i=1;i<=n;i++)
        viz[i]=0;

    BFS(x);
    fout<<viz[x];
    return 0;
}