Pagini recente » Cod sursa (job #1482937) | Cod sursa (job #874113) | Cod sursa (job #842100) | Cod sursa (job #2278761) | Cod sursa (job #2428475)
#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
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;
}
int main()
{
FILE* fin = fopen("darb.in", "r");
FILE* fout = fopen("darb.out", "w");
// citeste numarul de noduri si numarul de muchii
fscanf(fin, "%d", &n);
// citeste muchiile si construieste graful
for(int i = 0; i < n-1; i++)
{
// citeste muchia
int nod1, nod2;
fscanf(fin, "%d %d", &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
fprintf(fout, "%d", distMax);
fclose(fout);
fclose(fin);
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.