Pagini recente » Cod sursa (job #2663071) | Cod sursa (job #646961) | Cod sursa (job #2481921) | Cod sursa (job #3293956) | Cod sursa (job #1451090)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
static const int MAX_SIZE = 100000;
std::vector<int> nod[MAX_SIZE];
int tsize;
int diameter;
void readTree() {
ifstream fin("darb.in");
fin >> tsize;
for (int i = 0; i < tsize; ++i) {
int a, b;
fin >> a >> b;
nod[a].push_back(b);
nod[b].push_back(a);
}
fin.close();
}
int bfs(int root) {
std::queue<int> queue;
bool *vizited = new bool[tsize+1];
int *depth = new int[tsize+1];
memset(vizited, 0, sizeof(bool) * (tsize + 1));
memset(depth, 0, sizeof(int) * (tsize + 1));
queue.push(root);
vizited[root] = 1;
depth[root] = 1;
int el;
while (!queue.empty()) {
el = queue.front();
queue.pop();
for (int& i : nod[el]) {
if (!vizited[i]) {
vizited[i] = 1;
queue.push(i);
depth[i] = depth[el] + 1;
diameter = depth[i];
}
}
}
return el;
}
int main() {
readTree();
int l = bfs(1);
bfs(l);
ofstream fout("darb.out");
fout << diameter;
fout.close();
return 0;
}