Pagini recente » Cod sursa (job #755847) | Monitorul de evaluare | Cod sursa (job #301831) | Cod sursa (job #3132556) | Cod sursa (job #1551696)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int n;
vector<int> v[100001];
int marked[100001], len[100001];
queue<int> q;
int maxlen, maxnode;
int main()
{
ifstream cin ("darb.in");
ofstream cout ("darb.out");
cin >> n;
int x, y;
int i;
for (i = 1; i < n; ++i)
{
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
q.push(1);
marked[1] = 1;
while (!q.empty())
{
int node = q.front();
q.pop();
for (vector<int>::iterator it = v[node].begin(); it != v[node].end(); ++it)
{
int k = *it;
if (marked[k] == 0)
{
len[k] = len[node] + 1;
marked[k] = 1;
q.push(k);
if (maxlen < len[k])
{
maxlen = len[k];
maxnode = k;
}
}
}
}
for (i = 1; i <= n; ++i)
{
len[i] = 0;
marked[i] = 0;
}
q.push(maxnode);
marked[maxnode] = 1;
len[maxnode] = 1;
int diameter = 0;
while (!q.empty())
{
int node = q.front();
q.pop();
for (vector<int>::iterator it = v[node].begin(); it != v[node].end(); ++it)
{
int k = *it;
if (marked[k] == 0)
{
marked[k] = 1;
len[k] = len[node] + 1;
q.push(k);
if (diameter < len[k])
diameter = len[k];
}
}
}
cout << diameter;
return 0;
}