Pagini recente » Cod sursa (job #637486) | Cod sursa (job #1866262) | Cod sursa (job #450958) | Cod sursa (job #2362126) | Cod sursa (job #1424013)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector<int> drumuri[100001];
int totaldrumuri[100001];
vector<int> frunze;
int lungime[100001];
int tata[100001];
void explora(int loc,int t)
{
tata[loc]=t;
int i;
bool efrunza=true;
for (i=0;i<drumuri[loc].size();i++)
{
if (drumuri[loc][i]!=t)
{
efrunza=false;
explora(drumuri[loc][i],loc);
}
}
if (efrunza==true)
{
frunze.push_back(loc);
}
}
int main()
{
ifstream in("darb.in");
ofstream out("darb.out");
int i,n,x,y,drummaxim=0;
in>>n;
for (i=1;i<n;i++)
{
in>>x;
in>>y;
drumuri[x].push_back(y);
totaldrumuri[x]++;
drumuri[y].push_back(x);
totaldrumuri[y]++;
}
explora(1,0);
for (i=0;i<frunze.size();i++)
{
drummaxim=max(drummaxim,lungime[frunze[i]]+1);
drummaxim=max(drummaxim,lungime[tata[frunze[i]]]+1+lungime[frunze[i]]+1);
lungime[tata[frunze[i]]]=max(lungime[tata[frunze[i]]],lungime[frunze[i]]+1);
totaldrumuri[tata[frunze[i]]]--;
if (totaldrumuri[tata[frunze[i]]]==1)
{
frunze.push_back(tata[frunze[i]]);
}
}
out<<drummaxim;
}