Pagini recente » Cod sursa (job #2367071) | Teme Pregatire ACM Unibuc 2014, Anul I | Cod sursa (job #597856) | Istoria paginii runda/cner12a/clasament | Cod sursa (job #2189006)
#include <iostream>
#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 setN(int N)
{
n = N;
}
void add(int a, int b)
{
++n;
adjList[a].push_back(b);
adjList[b].push_back(a);
}
int mDistantaCeaMaiMare(int &start)
{
vector<int> v(n, 0);
vector<int> d(n, 0);
v[start] = 1;
int distantaCeaMaiMare = 0;
int celMaiIndepartatNod = 0;
queue<int> BFS;
BFS.push(start);
while(!BFS.empty())
{
int nodCurent = BFS.front();
for(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()
{
int N;
Graf arb;
freopen("darb.in", "r", stdin);
freopen("darb.out", "w", stdout);
cin >> N;
for(int i = 0; i < N - 1; ++i)
{
int a, b;
cin >> a >> b;
arb.add(--a, --b);
}
cout << arb.diametru();
return 0;
}