Pagini recente » Cod sursa (job #2788349) | Cod sursa (job #669617) | Cod sursa (job #2507036) | Cod sursa (job #813998) | Cod sursa (job #1234408)
#include <fstream>
#include <iostream>
#include <queue>
#include <bitset>
#include <list>
#define SIZE 100001
using namespace std;
int n;
bitset<SIZE> VIZ;
list<int>* 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();
list<int>* neighbors = ADJ[last_node];
if (neighbors)
{
for (list<int>::iterator it = neighbors->begin(); it != neighbors->end(); ++it)
{
int u = *it;
if (!VIZ[u])
{
Q->push(u);
VIZ[u] = 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;
list<int>* neighbors = ADJ[node];
if (neighbors)
{
for (list<int>::iterator it = neighbors->begin(); it != neighbors->end(); ++it)
{
int u = *it;
if (!VIZ[u])
{
Q->push(make_pair(u, dist + 1));
VIZ[u] = 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;
if (ADJ[a] == 00)
ADJ[a] = new list<int>();
if (ADJ[b] == 00)
ADJ[b] = new list<int>();
ADJ[a]->push_back(b);
ADJ[b]->push_back(a);
}
int last_node = last_node_from_bfs(1);
VIZ.reset();
int path_length = max_length_from_bfs(last_node);
ofs << path_length;
return 0;
}