Cod sursa(job #2814229)

Utilizator Theo_FurtunaTheodor-Florentin Furtuna Theo_Furtuna Data 7 decembrie 2021 19:49:54
Problema Diametrul unui arbore Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
    int maxim;
    int start;
    int noduri;
    int okey[100000];
    vector<int> adiacenta[100000];
    void citire_arbore()
    {
        in >> noduri;
        //okey.resize(noduri + 1);
        for (int i = 1; i < noduri; i++)
            adiacenta[i].resize(noduri + 1);
        for (int i = 1; i < noduri; i++)
        {
            int x, y;
            in >> x >> y;
            adiacenta[x].push_back(y);
            adiacenta[y].push_back(x);
            //okey.push_back(0);
        }
        //okey.push_back(0);
    }
    void DFS_arbore(int nod, int distanta)
    {
        okey[nod] = 1;
        if (distanta > maxim)
        {
            maxim = distanta;
            start = nod;
        }
        okey[nod] = 1;
        for (int i = 0; i < adiacenta[nod].size(); i++)
            if (!okey[adiacenta[nod][i]])
                DFS_arbore(adiacenta[nod][i], distanta + 1);
        //okey[nod] = 0;
    }
    void afisare_diametru()
    {
        /*for (int i = 0; i < noduri; i++)
            DFS_arbore(i, 0);
        out << maxim + 1;*/
        DFS_arbore(1, 0);
        for (int i = 1; i <= noduri; i++)
            okey[i] = 0;
        maxim = 0;
        DFS_arbore(start, 0);
        out << maxim + 1;
    }
int main()
{
	citire_arbore();
	afisare_diametru();
	return 0;
}