Pagini recente » Cod sursa (job #152737) | Cod sursa (job #2793870) | Cod sursa (job #3136863) | Cod sursa (job #2622791) | Cod sursa (job #3229450)
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
class Solutuion {
private:
size_t N;
size_t M;
vector<vector<size_t>> adj;
public:
explicit Solutuion(ifstream &in) {
in >> N;
adj.resize(N + 1);
size_t node1, node2;
for (size_t i = 1; i <= N - 1; i++) {
in >> node1 >> node2;
adj[node1].push_back(node2);
adj[node2].push_back(node1);
}
}
int solve() {
vector<int> d(N + 1, -1);
d[1] = 0;
queue<int> q;
q.push(1);
int dist = 1;
int prev_children = 1;
int next_children = 0;
while(!q.empty()) {
int curr_node = q.front();
q.pop();
for (auto neigh : adj[curr_node]) {
if (d[neigh] != -1)
continue;
d[neigh] = dist;
next_children++;
q.push(neigh);
}
if (--prev_children == 0) {
prev_children = next_children;
next_children = 0;
dist++;
}
}
size_t leaf1 = distance(d.begin(), max_element(d.begin(), d.end()));
q = queue<int>();
q.push(leaf1);
d = vector<int>(N + 1, -1);
d[leaf1] = 0;
dist = 1;
prev_children = 1;
next_children = 0;
while(!q.empty()) {
int curr_node = q.front();
q.pop();
for (auto neigh : adj[curr_node]) {
if (d[neigh] != -1)
continue;
d[neigh] = dist;
next_children++;
q.push(neigh);
}
if (--prev_children == 0) {
prev_children = next_children;
next_children = 0;
dist++;
}
}
return *max_element(d.begin(), d.end()) + 1;
}
};
int main() {
ifstream in("darb.in");
ofstream out("darb.out");
int solution = Solutuion(in).solve();
out << solution << endl;
in.close();
out.close();
return 0;
}