Pagini recente » Cod sursa (job #1674228) | Cod sursa (job #1458629) | Cod sursa (job #2692960) | Cod sursa (job #2743615) | Cod sursa (job #1389679)
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
ifstream is("darb.in");
ofstream os("darb.out");
int n;
vector<vector<int> > g;
bitset<100000> sel;
vector<int> d;
int lmax = 0;
int poz;
void Bf(int x);
int main()
{
is >> n;
g = vector<vector<int>>(n+1);
d = vector<int>(n+1, INF);
int x, y;
for(int i = 1; i < n; ++i)
{
is >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
Bf(1);
for(int j = 1; j <= n; ++j)
{
if(d[j] > lmax)
{
lmax = d[j];
poz = j;
}
}
lmax = 0;
Bf(poz);
for(int j = 1; j <= n; ++j)
{
lmax = max(lmax, d[j]);
}
os << lmax+1;
is.close();
os.close();
return 0;
}
void Bf(int x)
{
queue<int> Q;
for(int i = 1; i <= n; ++i)
d[i] = INF;
sel.reset();
sel[x] = 1;
d[x] = 0;
Q.push(x);
while(!Q.empty())
{
x = Q.front();
Q.pop();
for(const auto & y : g[x])
{
if(!sel[y] && d[y] > d[x] + 1)
{
sel[y] = 1;
d[y] = d[x] + 1;
Q.push(y);
}
}
}
}