Cod sursa(job #2203793)

Utilizator AlexGAlexandru Gheorghe AlexG Data 13 mai 2018 11:04:06
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>

using namespace std;

void citeste(ifstream &fin, vector<vector<int>> &listeAdiacenta)
{
    int n;
    fin >> n;
    listeAdiacenta.resize(n+1);
    int m;
    fin >> m;
    for(int i=0; i<m; i++)
    {
        int x, y;
        fin >> x >> y;
        listeAdiacenta[x].push_back(y);
        listeAdiacenta[y].push_back(x);
    }
}

int celMaiDepartatNod(int nodStart, const vector<vector<int>> &listeAdiacenta, vector<int> &tata)
{
    queue<int> coada;
    coada.push(nodStart);
    tata.resize(listeAdiacenta.size());
    tata[nodStart] = 0;
    vector<bool> esteVizitat(listeAdiacenta.size(), false);
    int noduriVizitate = 0;
    while(noduriVizitate < listeAdiacenta.size()-2)
    {
        int nodCurent = coada.front(), lungimeLista = listeAdiacenta[nodCurent].size();
        esteVizitat[nodCurent] = true;
        noduriVizitate++;
        for(int i=0; i<lungimeLista; i++)
        {
            int vecin = listeAdiacenta[nodCurent][i];
            if(!esteVizitat[vecin])
            {
                tata[vecin] = nodCurent;
                coada.push(vecin);
            }
        }
        coada.pop();
    }
    return coada.front();
}

int diametru(const vector<int> &tata, int nodGasit)
{
    if(tata[nodGasit])
        return 1+diametru(tata, tata[nodGasit]);
    return 1;
}

int main()
{
    ifstream fin("darb.in");
    vector<vector<int>> listeAdiacenta;
    citeste(fin, listeAdiacenta);
    vector<int> tata;
    int nodGasit = celMaiDepartatNod(1, listeAdiacenta, tata);
    nodGasit = celMaiDepartatNod(nodGasit, listeAdiacenta, tata);
    ofstream fout("darb.out");
    fout << diametru(tata, nodGasit);
    return 0;
}