Pagini recente » Cod sursa (job #682746) | Profil Hori42 | Cod sursa (job #1124064) | Istoria paginii utilizator/cameliagroza | Cod sursa (job #1565629)
#include <fstream>
#include <vector>
using namespace std;
const int MAXN = 100005;
ifstream in("darb.in");
ofstream out("darb.out");
int n;
vector<int> vecini[MAXN];
void citire()
{
in >> n;
int x,y;
for (int i = 1;i < n;++i)
{
in >> x >> y;
vecini[x].push_back(y);
vecini[y].push_back(x);
}
}
void dfs(int &ultim, int &diametru)
{
bool vizitat[MAXN] = {0};
int coada[MAXN] = {0};
int dist[MAXN] = {0};
int p = 1, q = 1;
coada[1] = ultim;
vizitat[ultim] = true;
dist[ultim] = 1;
diametru = 0;
while (p <= q)
{
int nod = coada[p];
coada[p++] = 0;
for (unsigned int i = 0;i < vecini[nod].size();++i)
{
int vecin = vecini[nod][i];
if (vizitat[vecin])
continue;
dist[vecin] = dist[nod] + 1;
vizitat[vecin] = true;
coada[++q] = vecin;
if (dist[vecin] > diametru)
{
diametru = dist[vecin];
ultim = vecin;
}
}
}
}
int main()
{
citire();
int ultim, diametru;
ultim = 1;
dfs(ultim, diametru);
dfs(ultim, diametru);
out << diametru << '\n';
return 0;
}