Cod sursa(job #2814966)

Utilizator asdfsfafafafafafafafaJarca Andrei asdfsfafafafafafafafa Data 8 decembrie 2021 21:34:54
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
class grafMare
{
    int N,M;
    vector <int> graf[100001];
    public:
        grafMare(){};
        void citireBFS(int,int&,int&);
        void citire();
};
void grafMare::citire()
{
    fin>>N;
    for(int i=0;i<N;i++)
    {
        int a,b;
        fin>>a>>b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
}
void grafMare::citireBFS(int start,int &end, int &d)
{
    
    int sol[100001];
    for(int i=0;i<N+1;i++)
        sol[i]=0;
    queue <int> q;
    q.push(start);
    sol[start]=0;
    
    while(!q.empty())
    {
        int first=q.front();
        q.pop();
        for(int vecin : graf[first])
        {
            if(sol[vecin]==0)
            {
                sol[vecin]=sol[first]+1;
                q.push(vecin);
            }
        }
    }
    d=0;
    for(int i=1;i<=N;i++)
        if(sol[i]>d)
        {
            d=sol[i];
            end=i;
        }
}
int main()
{
    grafMare gm;
    gm.citire();
    int end,d;
    int temp;
    gm.citireBFS(1,end,d);
    gm.citireBFS(end,temp,d);
    fout<<d;
}