Pagini recente » Cod sursa (job #2729588) | Cod sursa (job #3178128) | Cod sursa (job #613159) | Cod sursa (job #697993) | Cod sursa (job #2534500)
#include<fstream>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
pair <int, int> bfs_from(int start, vector <vector <int>> &ch, int n) {
//we remember the nodes we have seen
vector <int> seen(n, 0);
//we keep a queue with the node and the cur depth
queue <pair <int, int>> bfs;
bfs.push({start, 0});
seen[start] = 1;
pair <int, int> last_seen;
while (!bfs.empty()) {
last_seen = bfs.front();
bfs.pop();
int node = last_seen.first, depth = last_seen.second;
for (int i = 0; i < (int) ch[node].size(); i++) {
if (seen[ch[node][i]] == 0) {
bfs.push({ch[node][i], depth + 1});
seen[ch[node][i]] = 1;
}
}
}
return last_seen;
}
int main() {
ifstream fin("darb.in");
ofstream fout("darb.out");
int n; fin >> n;
vector <vector <int>> ch(n + 1, vector <int>());
for (int i = 0; i < n; i++) {
int a, b; fin >> a >> b;
ch[a].push_back(b);
ch[b].push_back(a);
}
int start = 1;
while (ch[start].size() == 0)
start++;
pair <int, int> one_end = bfs_from(start, ch, n + 1);
// cout << one_end.first << " " << one_end.second << "\n";
pair <int, int> deep_end = bfs_from(one_end.first, ch, n + 1);
// cout << deep_end.first << " " << deep_end.second << "\n";
fout << deep_end.second + 1 << "\n";
return 0;
}