Cod sursa(job #2812848)

Utilizator andreinovaNacu Andrei Emilian andreinova Data 5 decembrie 2021 12:17:48
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

#define MAX 100001
using namespace std;

ifstream indarb("darb.in");
ofstream outdarb("darb.out");

class Graf
{
    int NrNoduri;

public:
    vector<int> Adiacenta[MAX];

    Graf(int NrNoduri);

    void AdaugaMuchie(int nod, int nodConectat);
    void AdaugaMUchieNeorientat(int nod, int nodConectat);

    void Bfsdarb(int nod, int *nodinitial, int *nodfinal);

};

//ADAUGARE MUCHII
Graf::Graf(int NrNoduri)
{
    this->NrNoduri = NrNoduri;
}
void Graf::AdaugaMuchie(int nod, int nodConectat)
{
    Adiacenta[nod].push_back(nodConectat);
}

void Graf::AdaugaMUchieNeorientat(int nod, int nodConectat)
{
    Adiacenta[nod].push_back(nodConectat);
    Adiacenta[nodConectat].push_back(nod);
}

void Graf::Bfsdarb(int nod, int* nodinit, int *dist)
{
    int distanta[NrNoduri] = {0};
    distanta[nod] = 1;

    queue<int> Q;
    bool Vizitat[NrNoduri] = {0};

    Q.push(nod);
    Vizitat[nod] = 1;

    while(!Q.empty())
    {
        nod = Q.front();
        Q.pop();

        for(auto i: Adiacenta[nod])
        {
            if(!Vizitat[i])
            {
                Q.push(i);
                Vizitat[i] = 1;
                distanta[i] = distanta[nod] + 1;
            }
        }
    }

    int distMax = -1;
    int nodinitial;
    for(int i = 1; i < NrNoduri; i++)
        if(distanta[i] > distMax)
            {
                distMax = distanta[i];
                nodinitial = i;
            }

    *nodinit = nodinitial;
    *dist = distMax;
}

int main()
{

    int NrNoduri;
    indarb >> NrNoduri;

    Graf g(NrNoduri+1);
    int a, b;

    for(int i = 0; i < NrNoduri; i++)
    {
        indarb >> a >> b;
        g.AdaugaMUchieNeorientat(a, b);
    }

    int nodinit, dist;
    g.Bfsdarb(1, &nodinit, &dist);
    g.Bfsdarb(nodinit, &nodinit, &dist);
    outdarb << dist;

    return 0;
}