Cod sursa(job #2422727)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 19 mai 2019 19:49:12
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define Dim 100008
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int D[Dim],N,a,b,ans,cap,maxim=1;
bool viz[Dim];

vector < int > V[Dim];

void BFS()
{
    queue <int> qu;
    qu.push(1);
    viz[1]=1;
    while(!qu.empty())
    {
        int nod=qu.front();
        cap=nod;
        qu.pop();
        viz[nod]=1;
        for(unsigned int i=0;i<V[nod].size();i++)
        {
            int vecin=V[nod][i];
            if(!viz[vecin])
            {
                viz[vecin]=1;
                qu.push(vecin);
            }
        }

    }
}

int Diametru()
{
    D[1]=1;
    for(int i=1;i<=N;i++) viz[i]=0;

    queue < int > qu;
    qu.push(cap);
    viz[cap]=1;
    while(!qu.empty())
    {
        int nod=qu.front();
        qu.pop();
        viz[nod]=1;
        for(unsigned int i=0;i<V[nod].size();i++)
        {
            int vecin=V[nod][i];
            if(!viz[vecin])
            {
                D[vecin]=D[nod]+1;
                maxim=max(maxim,D[vecin]);
                viz[vecin]=1;
                qu.push(vecin);
            }
        }
    }
    return maxim;
}

int main()
{
    f>>N;
    for(int i=1;i<N;i++)
    {
        f>>a>>b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    BFS();
    g<<Diametru()+1;
    return 0;
}