Mai intai trebuie sa te autentifici.

Cod sursa(job #2814377)

Utilizator catarau.bianca.Bianca Catarau catarau.bianca. Data 7 decembrie 2021 23:32:01
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

#define NMax 100001

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

int n;
class graf
{
    int n;
    vector <int> muchii[NMax];

public:
    graf(int n);
    void bfs_darb(int s, int &ultim, int &dist_max);
    void darb();
};

graf :: graf(int n)
{
    this->n = n;
}

 void graf::bfs_darb(int s, int &ultim, int &dist_max) //am modificat primul bfs ca sa poata salva elem si dist pana la el
{
    dist_max=0;
    queue<int> q;
    int vizitat[NMax];
    int distanta[NMax];
    for (int i = 0; i < n; i++)
        {vizitat[i] = false;
        distanta[i]=0;}        //populeza vectorii si ii initializeaza ca si nevizitati
    q.push(s); //adaugam in coada s-ul de start si il marcam ca vizitat si distanta 0
    vizitat[s] = true;
    distanta[s] = 1;
    while (!q.empty()) //daca avem elemente in coada, executam:
    {
        int curent = q.front(); //nodul curent devine cel mai vechi nod adaugat in coada
        q.pop();
        //parcurgem lista de adicaneta pt a gasi varfurile adiacente nevizitate ale noduliui curent
        for (auto i:muchii[curent])
        {
            if (!vizitat[i])
            {
                vizitat[i] = true;
                q.push(i);
                distanta[i] = distanta[curent] + 1;
                if(distanta[i]>dist_max)        //atunci cand gasim dist max salvam dist si elem
                {
                    dist_max=distanta[i];
                    ultim=i;
                }
            }
        }
    }

}
void graf::darb(){
    int start_node, end_node, distanta_maxima;
    f >> n;

    int nod1, nod2;
    for(int i = 1; i <= n; ++i)
    {
        f >> nod1 >> nod2;
        muchii[nod1].push_back(nod2);
        muchii[nod2].push_back(nod1);
    }

    bfs_darb(1, start_node, distanta_maxima);       //bfs de la nod 1 la prim din bfs final
    bfs_darb(start_node, end_node, distanta_maxima); //bfs de la prim la ultimul nod din bfs final

    g << distanta_maxima;
}
int main()
{
    graf G(n);
    G.darb();
    return 0;
}