Pagini recente » Cod sursa (job #67067) | Cod sursa (job #561115) | Cod sursa (job #2153573) | Cod sursa (job #3222498) | Cod sursa (job #2910698)
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
const int NMAX=100001;
vector<int> graf[NMAX];
int d[NMAX];
queue<int> q;
int n;
void bfs(int s)
{
int x,y;
for(int i=1; i<=n; i++)
d[i]=-1;
//punem 0 la sursa
d[s]=0;
q.push(s);
while(q.empty()==false)
{
x=q.front();
q.pop();
//parcurg vecinii nodului x
for(int j=0; j<graf[x].size(); j++)
{
y=graf[x][j];
if(d[y]==-1 || d[y]>d[x]+1)
{
d[y]=d[x]+1;
q.push(y);
}
}
}
}
int main()
{
int x,y;
in>>n;
for(int i=1; i<=n-1; i++)
{
in>>x>>y;
//adaugam nodul y in lista de vecini ai nodului x
graf[x].push_back(y);
graf[y].push_back(x);
}
bfs(1);
int d_maxim=d[1];
int nod_dmax=1;
for(int i=2; i<=n; i++)
{
if(d_maxim< d[i])
{
d_maxim=d[i];
nod_dmax=i;
}
}
bfs(nod_dmax);
int diametru=d[1];
for(int i=1; i<=n; i++)
if(diametru<d[i])
diametru=d[i];
out<<diametru+1;
return 0;
}