Pagini recente » Cod sursa (job #2778207) | Cod sursa (job #1038530) | Cod sursa (job #1487906) | Cod sursa (job #634931) | Cod sursa (job #2407246)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int df(int a[][100000],int n,int d[],int x)
{
for(int i=1;i<=n;i++)
if(a[x][i] && d[i]==-1)
{
d[i]=d[x]+1;
df(a,n,d,i);
}
}
int a[100000][100000];
int main()
{
int d[100000],x,y,n,vf1,vf2,maxi=-1; ///vectorul d reprezinta vectorul de distante dintr-un anumit nod si toate celelalte;
fin>>n;
for(int i=1;i<=n;i++)
d[i]=-1; ///asftel, vom initializa acest vector cu -1, pentru ca 0 va fi distanta de la acel nod la el insusi;
d[1]=0;
for(int i=1;i<n;i++)
{
fin>>x>>y;
a[x][y]=a[y][x]=1; ///cream matricea de adiacenta a grafului;
}
df(a,n,d,1); ///parcurgem in adancime graful dintr-un nod oarecare, in acest caz 1;
for(int i=1;i<=n;i++)
if(d[i]>maxi)
{
maxi=d[i];
vf2=i; ///vom retine nodul cel mai indepartat de nodul 1, acesta fiind unul din varfurile celui mai lung lant;
}
for(int i=1;i<=n;i++) ///deoarece dorim sa mai facem o parcurgere in adancime din varful gasit mai sus, vom reinitializa vectorul cu -1, si cu 0 pe pozitia acelui varf;
d[i]=-1;
d[vf2]=0;
maxi=-1;
df(a,n,d,vf2); ///repetam parcurgerea, pornind din acel varf;
for(int i=1;i<=n;i++)
if(d[i]>maxi)
{
maxi=d[i];
vf1=i; ///asftfel, cel mai lung lant din acel arbore va avea celalalt varf in cel mai indepartat nod;
}
maxi++;
fout<<maxi; ///afisam cele doua capete si lungimea lantului cerut;
return 0;
}