Pagini recente » Cod sursa (job #778309) | Monitorul de evaluare | Cod sursa (job #808979) | Istoria paginii problema/chitooc | Cod sursa (job #1669697)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <string.h>
#include <ctime>
#include <stdlib.h>
#define MAX_N 1000001
using namespace std;
int n,m,last,diametru,visited1[MAX_N],visited2[MAX_N];
/*stack<int> s;*/
ifstream f("darb.in");
ofstream g("darb.out");
vector<vector<int> > graf;
void bfs(int x)
{
static int c=0;
memset(visited1,0,MAX_N);
memset(visited2,0,MAX_N);
int i,element,z,y=0;
if(x<0 ||x>n-1)
return ;
queue<int> q;
q.push(x);
visited1[x]=1;
visited2[x]=1;
while(!q.empty())
{
element=q.front();
/*z=0;*/
for(i=0; i<graf[element].size(); i++)
{
if(!visited2[graf[element][i]])
{
q.push(graf[element][i]);
visited1[graf[element][i]]=visited1[element]+1;
visited2[graf[element][i]]=1;
/*if(z==0 && c>0 && y!=visited1[graf[element][i]])
{
s.push(element);
z++;
}*/
diametru=visited1[graf[element][i]];
last=graf[element][i];
}
}
/*y=visited1[graf[element][i-1]];*/
q.pop();
}
/*if(c>0)
s.push(last);
c++;*/
}
/*void centru()
{
int a=diametru/2+1,b=diametru;
while(b>a)
{
s.pop();
b--;
}
}*/
int main()
{
int i,x,y,z;
f>>n;
m=n-1;
graf.resize(n);
for(i=0; i<m; i++)
{
f>>x>>y;
x--;
y--;
graf[x].push_back(y);
graf[y].push_back(x);
}
srand(time(NULL));
z=rand()%n;
bfs(z);
bfs(last);
g<<diametru;
/*g<<endl;
centru();
if(diametru%2==0)
{
g<<s.top()+1<<" ";
s.pop();
g<<s.top()+1<<" ";
}
else
{
g<<s.top()+1<<" ";
}*/
return 0;
}