Pagini recente » Profil andrici_cezar | Profil andrici_cezar | Autentificare | Cod sursa (job #1276768) | Cod sursa (job #3229056)
#include <bits/stdc++.h>
using namespace std;
class Task {
public:
void solve() {
read_input();
print_output(get_result());
}
private:
// numarul maxim de noduri
static constexpr int NMAX = (int)1e5 + 5; // 10^5 + 5 = 100.005
// n = numar de noduri, m = numar de muchii/arce
int n, m;
// adj[node] = lista de adiacenta a nodului node
// exemplu: daca adj[node] = {..., neigh, ...} => exista muchia (node, neigh)
vector<int> adj[NMAX];
void read_input() {
ifstream fin("darb.in");
fin >> n;
for (int i = 1, x, y; i <= n; i++) {
fin >> x >> y; // muchie (x, y)
adj[x].push_back(y);
adj[y].push_back(x); // graf neorientat
}
fin.close();
}
int bfs_getLast(int source) {
queue<int> q;
set<int> visited;
int last = 1;
q.push(source);
visited.insert(source);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neigh : adj[node]) {
// cout << "Neigh: " << neigh << ' ';
if (visited.find(neigh) == visited.end()) {
q.push(neigh);
visited.insert(neigh);
last = neigh;
// cout << "Last: " << last << '\n';
}
}
}
return last;
}
int bfs_getMaxDist(int source) {
int d = 0;
queue<int> q;
set<int> visited;
q.push(source);
while (!q.empty()) {
queue<int> q_aux;
d++;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neigh : adj[node]) {
if (visited.find(neigh) == visited.end()) {
q_aux.push(neigh);
visited.insert(neigh);
}
}
}
q = q_aux;
}
return d;
}
int get_result() {
int last = bfs_getLast(1);
// cout << "Last_end: " << last << '\n';
return bfs_getMaxDist(last);
}
void print_output(int d) {
ofstream fout("darb.out");
fout << d;
fout.close();
}
};
int main() {
auto* task = new (nothrow) Task(); // hint: cppreference/nothrow
if (!task) {
cerr << "new failed: WTF are you doing? Throw your PC!\n";
return -1;
}
task->solve();
delete task;
return 0;
}