Pagini recente » Rezultatele filtrării | Diferente pentru problema/dans intre reviziile 11 si 10 | Rezultatele filtrării | Cod sursa (job #553734) | Cod sursa (job #1095554)
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int N;
vector <int> G[100005];
queue <int> Q;
int Distance[100005];
bool Use[100005];
int PMax,Max;
void Read()
{
int i;
f>>N;
for(i=1;i<=N-1;i++)
{
int x,y;
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void FirstBFS()
{
Q.push(1);
Use[1]=1;
while(!Q.empty())
{
int node=Q.front();
Q.pop();
for(unsigned int i=0;i<G[node].size();i++)
{
int neighbour=G[node][i];
if(Use[neighbour]==0)
{
Distance[neighbour]=Distance[node]+1;
Q.push(neighbour);
Use[neighbour]=1;
if(Distance[neighbour]>Max)
{
Max=Distance[neighbour];
PMax=neighbour;
}
}
}
}
}
void SecondBFS()
{
Q.push(PMax);
Use[PMax]=1;
while(!Q.empty())
{
int node=Q.front();
Q.pop();
for(unsigned int i=0;i<G[node].size();i++)
{
int neighbour=G[node][i];
if(Use[neighbour]==0)
{
Distance[neighbour]=Distance[node]+1;
Q.push(neighbour);
Use[neighbour]=1;
Max=max(Max,Distance[neighbour]);
}
}
}
g<<Max+1<<"\n";
}
int main()
{
Read();
FirstBFS();
Max=0;
memset(Distance,0,sizeof(Distance));
memset(Use,0,sizeof(Use));
SecondBFS();
return 0;
}