Pagini recente » Cod sursa (job #2090931) | Cod sursa (job #415356) | Cod sursa (job #1763642) | Cod sursa (job #1226430) | Cod sursa (job #1095941)
#include<fstream>
using namespace std;
typedef struct celula {
int nod;
celula *next;
} *lista;
lista arb[100005],v;
int i,x,y,n,jos[100005],tata[100005];
bool viz[100005];
void dfs1(int nod) {
viz[nod]=1;
int act=0;
for (lista p=arb[nod]; p; p=p->next)
if (viz[p->nod]==0) { tata[p->nod]=nod; dfs1(p->nod); act=max(act,jos[p->nod]); }
jos[nod]=act+1;
}
int main(void) {
ifstream fin("darb.in");
ofstream fout("darb.out");
fin>>n;
for (i=1; i<n; ++i) {
fin>>x>>y;
v=new celula; v->nod=x; v->next=arb[y]; arb[y]=v;
v=new celula; v->nod=y; v->next=arb[x]; arb[x]=v;
}
dfs1(1);
int sol=0;
for (i=1; i<=n; ++i) {
int s1=0,s2=0,f1;
for (lista p=arb[i]; p; p=p->next)
if (p->nod!=tata[i]&&jos[p->nod]>s1) { s1=jos[p->nod]; f1=p->nod; }
for (lista p=arb[i]; p; p=p->next)
if (p->nod!=tata[i]&&jos[p->nod]>s2&&p->nod!=f1) s2=jos[p->nod];
sol=max(sol,s1+s2+1);
}
fout<<sol;
return(0);
}