Pagini recente » Cod sursa (job #155198) | Cod sursa (job #1889604) | Cod sursa (job #1124168) | Cod sursa (job #2511225) | Cod sursa (job #1205736)
#include <array>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
const int kMaxSize = 100000;
void read(int& tree_size, array<vector<int>, kMaxSize>& graph)
{
ifstream fin("darb.in");
fin >> tree_size;
for (int i = 0; i < tree_size - 1; ++i)
{
int x = 0, y = 0;
fin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
fin.close();
}
void write(const int& max_dist)
{
ofstream fout("darb.out");
fout << max_dist << '\n';
fout.close();
}
//returns a pair. First is the node and second is the distance
pair<int, int> bfs(const int& tree_size, const int& start,
const array<vector<int>, kMaxSize>& G)
{
int max_dist = -1;
array<bool, kMaxSize> seen;
fill(seen.begin(), seen.end(), false);
pair<int, int> farthest;
queue<pair<int, int>> q;
q.push(make_pair(start, 1));
while (!q.empty())
{
pair<int, int> front = q.front();
q.pop();
int u = front.first, dist = front.second;
if (dist > max_dist)
farthest = front;
for (const auto& v: G[u])
{
if (!seen[v])
{
seen[v] = true;
q.push(make_pair(v, dist + 1));
}
}
}
return farthest;
}
int main()
{
int tree_size = 0;
array<vector<int>, kMaxSize> t;
read(tree_size, t);
int u = bfs(tree_size, 1, t).first;
int max_dist = bfs(tree_size, u, t).second;
write(max_dist);
return 0;
}