Pagini recente » Cod sursa (job #1070960) | Cod sursa (job #2612629) | Cod sursa (job #1489297) | Cod sursa (job #769990) | Cod sursa (job #2189183)
#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
class Graf
{
int n, m;
vector<int> adjList[100001];
public:
Graf()
{
n = 0;
m = 0;
}
void add(int a, int b)
{
++m;
adjList[a].push_back(b);
adjList[b].push_back(a);
}
void setN(int N)
{
n = N;
}
int mDistantaCeaMaiMare(int &start)
{
// cout << start;
vector<int> v(n, 0);
vector<int> d(n, 0);
v[start] = 1;
d[start] = 1;
int distantaCeaMaiMare = 1 ;
int celMaiIndepartatNod = start;
queue<int> BFS;
BFS.push(start);
while(!BFS.empty())
{
int nodCurent = BFS.front();
for(unsigned int i = 0; i < adjList[nodCurent].size(); ++i)
{
int nodUrmator = adjList[nodCurent][i];
if(!v[nodUrmator]) {
v[nodUrmator] = 1;
BFS.push(nodUrmator);
d[nodUrmator] = d[nodCurent] + 1;
if(d[nodUrmator] > distantaCeaMaiMare) {
distantaCeaMaiMare = d[nodUrmator];
celMaiIndepartatNod = nodUrmator;
}
}
}
BFS.pop();
}
start = celMaiIndepartatNod;
return distantaCeaMaiMare;
}
int diametru()
{
int start = 0;
mDistantaCeaMaiMare(start);
return mDistantaCeaMaiMare(start);
}
};
int main()
{
fstream f("darb.in", ios::in);
fstream g("darb.out", ios::out);
int N;
Graf arb;
f >> N;
arb.setN(N);
for(int i = 0; i < N - 1; ++i)
{
int a, b;
f >> a >> b;
arb.add(--a, --b);
}
g << arb.diametru();
return 0;
}