Pagini recente » Cod sursa (job #1033844) | Cod sursa (job #1911871) | Cod sursa (job #1178981) | Cod sursa (job #1184396) | Cod sursa (job #2203800)
#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);
for(int i=0; i<n-1; 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);
unsigned 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;
}