Pagini recente » Cod sursa (job #761004) | Cod sursa (job #1754205) | Cod sursa (job #2745428) | Cod sursa (job #2309345) | Cod sursa (job #2834094)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
#define MAX_N 100001
vector<vector<int>> tree(MAX_N);
int diameter;
int BFS(int begin) {
vector<bool> visited(MAX_N);
queue<int> myQueue;
int last;
myQueue.push(begin);
while (!myQueue.empty()) {
int element = myQueue.front();
for (int i = 0; i < tree[element].size(); ++i) {
if (visited[tree[element][i]] == false) {
visited[tree[element][i]] = true;
myQueue.push(tree[element][i]);
last = tree[element][i];
}
}
myQueue.pop();
}
return last;
}//in this function, I will be looking for the most far away leaf
vector<int>visited(MAX_N);
void DFS(int node, int cnt) {
visited[node] = true;
if (tree[node].size() == 1 ) {
diameter = max(cnt, diameter);
cnt = 0;
}
for (int i = 0; i < tree[node].size(); ++i) {
if (visited[tree[node][i]] == false) {
DFS(tree[node][i], cnt + 1);
}
}
}
int main() {
int n;
fin >> n;
for (int i = 1, x, y; i < n; ++i) {
fin >> x >> y;
tree[x].push_back(y);
tree[y].push_back(x);
}
DFS(BFS(4), 0);
fout << diameter + 1;
return 0;
}