Pagini recente » Cod sursa (job #1935811) | Cod sursa (job #2098579) | Cod sursa (job #2201973) | Cod sursa (job #2195921) | Cod sursa (job #2190676)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stdio.h>
#define INF 0x7fffffff
#define NMAX 100002
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
struct Nod {
int nod;
int distanta;
bool operator<(const Nod &o) const
{
return distanta > o.distanta;
}
};
vector < vector < int > > G(NMAX);
vector < int > dist(NMAX, 0);
vector < bool > vizitat(NMAX);
vector < int > cnt_nod_inQ(NMAX, 0);
int n, m, s;
bool compare (const Nod& a, const Nod& b) {
return a.distanta < b.distanta;
}
void read() {
FILE * pFile;
pFile = fopen("darb.in", "r");
//f >> n >> m;
fscanf(pFile, "%d", &n);
int x = 0, y = 0, dist = 0;
Nod nod_pereche;
m = n - 1;
while (m--) {
fscanf(pFile, "%d %d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
}
Nod constructNode(int nod, int distanta) {
Nod new_node;
new_node.nod = nod;
new_node.distanta = distanta;
return new_node;
}
void bfs(int nod_sursa) {
queue<int> qNode;
qNode.push(nod_sursa);
vizitat[nod_sursa] = true;
while (!qNode.empty()) {
int nod = qNode.front();
qNode.pop();
for (int i = 0; i < G[nod].size(); i++) {
int nodVecin = G[nod][i];
if (!vizitat[nodVecin]) {
vizitat[nodVecin] = true;
dist[nodVecin] = dist[nod] + 1;
qNode.push(nodVecin);
}
}
}
/*FILE * pFile;
pFile = fopen("bfs.out", "w");
for (int i = 1; i <= n; i++) {
if (!dist[i] && i != s) {
dist[i] = -1;
}
fprintf(pFile, "%d ", dist[i]);
}*/
}
int main()
{
read();
bfs(1);
dist.clear();
vizitat.clear();
int maxim = -1, nodMax = 0;
for (int i = 2; i <= n; i++){
if (dist[i] > maxim) {
maxim = dist[i];
nodMax = i;
}
}
for (int i = 0; i <= NMAX; i++) {
dist.push_back(0);
vizitat.push_back(false);
}
bfs(nodMax);
maxim = -1, nodMax = 0;
for (int i = 1; i <= n; i++){
if (dist[i] > maxim) {
maxim = dist[i];
nodMax = i;
}
}
g << maxim + 1;
return 0;
}