Pagini recente » Cod sursa (job #1328689) | Cod sursa (job #1025978) | Cod sursa (job #2338585) | Cod sursa (job #2838406) | Cod sursa (job #2428474)
#include <vector>
#include <fstream>
// numarul maxim de noduri in arbore
#define MAX_N 100005
using namespace std;
// numarul de noduri in arbore si numarul de muchii
int n;
// graful memorat prin liste de adiacenta
vector<int> graf[MAX_N];
// daca un nod a fost deja parcurs
bool parcurs[MAX_N];
// distanta maxima
int distMax = -1;
// nodul din care pornest solutia
int solutie = -1;
// parcurge o data si gaseste solutia
int Solutie(int nod)
{
// daca ndul nu a fost parcurs il parcurge
if(!parcurs[nod])
{
int maxNod1 = -1;
int maxVal1 = -1;
int maxNod2 = -1;
int maxVal2 = -1;
parcurs[nod] = true;
// cauta copiii acestui nod care au valorile
// cele mai mari
for(int i = 0; i < graf[nod].size(); i++)
{
// daca nodul nu a fost parcurs il parcurge
// si ii afla valoarea
int nod2 = graf[nod][i];
if(!parcurs[nod2])
{
int val = Solutie(nod2);
// daca e valoare maxima
if(val >= maxVal1)
{
// schimba a doua valoare maxima
maxVal2 = maxVal1;
maxNod2 = maxNod1;
maxVal1 = val;
maxNod1 = nod2;
}
else
{
if(val >= maxVal2)
{
maxVal2 = val;
maxNod2 = nod2;
}
}
}
}
// calculeaza valoarea drumului maxim in punct
int dist = 1;
if(maxNod1 != -1)
{
dist += maxVal1;
if(maxNod2 != -1)
dist += maxVal2;
}
// daca e solutie
if(dist > distMax)
{
distMax = dist;
solutie = nod;
}
// calculeaza rezultatul in nod
int result = 1;
if(maxVal1 + 1 > result)
result = maxVal1 + 1;
return result;
}
return 0;
}
int main()
{
ifstream fin("darb.in");
ofstream fout("darb.out");
// citeste numarul de noduri si numarul de muchii
fin >> n;
// citeste muchiile si construieste graful
for(int i = 0; i < n-1; i++)
{
// citeste muchia
int nod1, nod2;
fin >> nod1 >> nod2;
// adauga nodurile in grad
graf[nod1].push_back(nod2);
graf[nod2].push_back(nod1);
}
// presupune ca nodul 1 este radacina arborelui. Programul
// presupune ca agraful chiar are structura de arbore (este aciclic, neorientat si
// conex)
Solutie(1);
// afiseaza distanta maxima
fout << distMax << endl;
fout.close();
fin.close();
return 0;
}
// Complexitate O(n). Algoritmul parcurge fiecare copil si afla lungimea de
// la el pana la cea mai departata frunza si verifica daca acea
// lungime + lungimea altui copil pana la cea mai departata frunza constituie
// solutia. Dupa ce gaseste solutia o parcurge.