Pagini recente » Cod sursa (job #2167793) | Cod sursa (job #2507837) | Cod sursa (job #72762) | Cod sursa (job #975019) | Cod sursa (job #2924179)
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
deque<int> q;
vector<int> neighbors[100000];
int n, x, y, visited[100000], counter[100000], last_visited_node, diameter;
void bfs(int starting_node) {
q.push_back(starting_node);
visited[starting_node] = 1;
counter[starting_node] = 1;
while (!q.empty()) {
/*
cout << "Current Node: " << q.front() + 1;
cout << "\nIts neighbors: ";
for (int i = 0; i < neighbors[q.front()].size(); ++i) {
cout << neighbors[q.front()][i] + 1 << ' ';
}
cout << "\nCurrent Queue: ";
for (int i = 0; i < q.size(); ++i) {
cout << q[i] + 1 << ' ';
}
*/
int current_size = neighbors[q.front()].size();
for (int i = 0; i < current_size; ++i) {
if (!visited[neighbors[q.front()][i]]) {
q.push_back(neighbors[q.front()][i]);
visited[neighbors[q.front()][i]] = 1;
counter[neighbors[q.front()][i]] = counter[q.front()] + 1;
}
diameter = counter[q.front()];
last_visited_node = q.front();
}
q.pop_front();
/*
cout << "\nNew Queue: ";
for (int i = 0; i < q.size(); ++i) {
cout << q[i] + 1 << ' ';
}
cout << "\nlast: " << last_visited_node + 1;
cout << "\ndiameter: " << diameter << "\n\n";
*/
}
}
void reset() {
for (int i = 0; i < n; ++i) {
visited[i] = 0;
}
}
int main() {
ifstream fin("darb.in");
ofstream fout("darb.out");
fin >> n;
for (int i = 1; i < n; ++i) {
fin >> x >> y;
neighbors[x - 1].push_back(y - 1);
neighbors[y - 1].push_back(x - 1);
}
bfs(0);
reset();
bfs(last_visited_node);
fout << diameter;
return 0;
}