Cod sursa(job #2659588)

Utilizator mihaifluturFlutur Mihail mihaiflutur Data 17 octombrie 2020 10:44:43
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
std::ifstream fin("darb.in");
std::ofstream fout("darb.out");
#include <vector>
const int nmax=100000;
std::vector<int> V[nmax+1];
int D[nmax+1];
#include <queue>
std::queue<int> Q;
#include <string.h>
void BFS(int nod)
{
    memset(D,-1,sizeof(D));
    Q.push(nod);
    D[nod]=0;
    while(!Q.empty())
    {
        int Nod=Q.front();
        Q.pop();
        for(int i=0;i<(int)V[Nod].size();i++)
        {
            int vecin=V[Nod][i];
            if(D[vecin]==-1)
            {
                D[vecin]=D[Nod]+1;
                Q.push(vecin);
            }
        }
    }
}
int main()
{
    int n,x,y;
    fin>>n;
    while(fin>>x>>y)
    {
        V[x].push_back(y);
        V[y].push_back(x);
    }
    BFS(1);
    int maxi=0,frmax=0;
    for(int i=1;i<=n;i++)
        if(maxi<D[i])
        {
            maxi=D[i];
            frmax=i;
        }
    BFS(frmax);
    maxi=0;
    for(int i=1;i<=n;i++)
        maxi=std::max(maxi,D[i]);
    fout<<maxi+1<<"\n";
    return 0;
}