Pagini recente » simulare_lot_seniori_2 | Cod sursa (job #1898403) | Cod sursa (job #3167019) | Cod sursa (job #2702437) | Cod sursa (job #1234358)
#include <fstream>
#include <iostream>
#include <queue>
#include <bitset>
#define SIZE 100001
using namespace std;
int n;
bitset<SIZE> VIZ;
bitset<SIZE> ADJ[SIZE];
int last_node_from_bfs(int v)
{
queue<int>* Q = new queue<int>();
Q->push(v);
VIZ[v] = true;
int last_node;
while (!Q->empty())
{
last_node = Q->front(); Q->pop();
for (int i = 1; i <= n; ++i)
{
if (ADJ[last_node][i] && !VIZ[i])
{
Q->push(i);
VIZ[i] = true;
}
}
}
return last_node;
}
int max_length_from_bfs(int v)
{
queue<pair<int, int> >* Q = new queue<pair<int, int> >();
Q->push(make_pair(v, 1));
VIZ[v] = true;
pair<int, int> p;
while (!Q->empty())
{
p = Q->front(); Q->pop();
int node = p.first;
int dist = p.second;
for (int i = 1; i <= n; ++i)
{
if (ADJ[node][i] && !VIZ[i])
{
Q->push(make_pair(i, dist + 1));
VIZ[i] = true;
}
}
}
return p.second;
}
int main()
{
ifstream ifs("darb.in");
ofstream ofs("darb.out");
ifs >> n;
for (int i = 0; i < n; ++i)
{
int a, b;
ifs >> a >> b;
ADJ[a][b] = ADJ[b][a] = true;
}
int last_node = last_node_from_bfs(1);
VIZ.reset();
int path_length = max_length_from_bfs(last_node);
ofs << path_length;
return 0;
}