Pagini recente » Cod sursa (job #1653354) | Cod sursa (job #602141) | Cod sursa (job #1725364) | Cod sursa (job #2213116) | Cod sursa (job #2980695)
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
const int NMAX = 100000;
vector <int> muchii[NMAX + 1];
queue <int> coada;
bool vizitat[NMAX + 1];
int contor[NMAX + 1];
int n, x, y, last, diametru;
void breadth_first_search(int node_start)
{
memset(vizitat, 0, NMAX);
memset(contor, 0, NMAX);
coada.push(node_start);
vizitat[node_start] = true;
contor[node_start] = 1;
while(!coada.empty())
{
int varf = coada.front();
for(auto next_node : muchii[varf])
{
if(!vizitat[next_node])
{
coada.push(next_node);
contor[next_node] = contor[varf] + 1;
vizitat[next_node] = true;
diametru = contor[next_node];
last = next_node;
}
}
coada.pop();
}
}
int main()
{
in >> n;
for(int i = 0; i < n - 1; i++)
{
in >> x >> y;
muchii[x].push_back(y);
muchii[y].push_back(x);
}
breadth_first_search(1);
breadth_first_search(last);
out << diametru;
in.close();
out.close();
return 0;
}