Pagini recente » Cod sursa (job #2315956) | Cod sursa (job #2383990) | Cod sursa (job #2790829) | Cod sursa (job #1281578) | Cod sursa (job #2960576)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int MAX_SIZE = 100001;
queue<int> nodes;
vector<int> neighbors[MAX_SIZE];
int n, visited[MAX_SIZE], level[MAX_SIZE], last_visited_node, diameter;
void bfs(int starting_node) {
nodes.push(starting_node);
visited[starting_node] = 1;
level[starting_node] = 1;
while (!nodes.empty()) {
/*
cout << "Current Node: " << nodes.front();
cout << "\nIts neighbors: ";
for (int i = 0; i < neighbors[nodes.front()].size(); ++i) {
cout << neighbors[nodes.front()][i] << ' ';
}
cout << "\nCurrent Queue: ";
for (int i = 0; i < nodes.size(); ++i) {
cout << nodes[i] << ' ';
}
*/
int curr_node = nodes.front();
int curr_neighbors_num = neighbors[curr_node].size();
nodes.pop();
for (int i = 0; i < curr_neighbors_num; ++i) {
if (!visited[neighbors[curr_node][i]]) {
nodes.push(neighbors[curr_node][i]);
visited[neighbors[curr_node][i]] = 1;
level[neighbors[curr_node][i]] = level[curr_node] + 1;
}
diameter = level[curr_node];
last_visited_node = curr_node;
}
/*
cout << "\nNew Queue: ";
for (int i = 0; i < nodes.size(); ++i) {
cout << nodes[i] << ' ';
}
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) {
int x, y;
fin >> x >> y;
neighbors[x].push_back(y);
neighbors[y].push_back(x);
}
/*
for (int i = 1; i <= n; ++i) {
cout << "Neighbors of node " << i << " are: ";
for (int j = 0; j < neighbors[i].size(); ++j) {
cout << neighbors[i][j] << ' ';
}
cout << '\n';
}
*/
bfs(1);
reset();
bfs(last_visited_node);
fout << diameter;
return 0;
}