Pagini recente » Cod sursa (job #1917221) | Clasamentul arhivei Infoarena Monthly | Cod sursa (job #1732312) | Cod sursa (job #3187881) | Cod sursa (job #2424706)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int n;
int viz[100005], dist[100005];
vector<int> Graph[100005];
queue <int> MyQueue;
void Citire()
{
int x1,x2;
f >> n;
for(int i=0;i<n-1;i++)
{
f >> x1 >> x2;
Graph[x1].push_back(x2);
Graph[x2].push_back(x1);
}
}
void Init()
{
for(int i=1;i<=n;i++)
{
viz[i] = 0;
dist[i] = 0;
}
}
void BFS(int start)
{
int node;
viz[start] = 1;
dist[start] = 0;
MyQueue.push(start);
while(!MyQueue.empty())
{
node = MyQueue.front();
MyQueue.pop();
for(int i=0;i<Graph[node].size();i++)
{
int nn = Graph[node][i];
if(viz[nn] == 0)
{
viz[nn] = 1;
dist[nn] = dist[node] + 1;
MyQueue.push(nn);
}
}
}
}
void DFS(int node)
{
viz[node] = 1;
for(int i=0;i<Graph[node].size();i++)
{
int nn = Graph[node][i];
if(viz[nn] == 0)
{
dist[nn] = dist[node] + 1;
DFS(nn);
}
}
}
int main()
{
int maxim = -1, nodFar;
Citire();
Init();
BFS(1);
for(int i=1;i<=n;i++)
{
if(dist[i] > maxim)
{
maxim = dist[i];
nodFar = i;
}
}
Init();
dist[nodFar] = 0;
DFS(nodFar);
for(int i=1;i<=n;i++)
{
if(dist[i] > maxim)
{
maxim = dist[i];
}
}
g << maxim+1;
return 0;
}