Pagini recente » Cod sursa (job #1102140) | Cod sursa (job #2702745) | Cod sursa (job #3136831) | Cod sursa (job #726443) | Cod sursa (job #2271747)
#include <fstream>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
struct Node{
int node;
Node *next;
}*G[100001];
int N;
int finalDistance;
int furthestNodeFrom(int v)
{
int Q[100000];
bool isVisited[100001];
for(int i=1; i<=N; i++)
isVisited[i] = false;
isVisited[v] = true;
int dist[100001];
dist[v] = 0;
int first = 0;
int last = 0;
Q[first] = v;
int maxDistance = 0;
int furthestNode;
while(first<=last)
{
for(Node *p = G[Q[first]]; p!=0; p = p->next)
if(!isVisited[p->node])
{
last++;
Q[last] = p->node;
isVisited[p->node] = true;
dist[p->node] = dist[Q[first]] + 1;
if(dist[p->node] > maxDistance)
{
maxDistance = dist[p->node];
furthestNode = p->node;
}
}
first++;
}
finalDistance = maxDistance;
return furthestNode;
}
int main()
{
fin >> N;
for(int k=1; k<=N-1; k++)
{
int v, w;
fin >> v >> w;
Node *p = new Node;
p->node = w;
p->next = G[v];
G[v] = p;
p = new Node;
p->node = v;
p->next = G[w];
G[w] = p;
}
int chainStart = furthestNodeFrom(1);
int chainEnd = furthestNodeFrom(chainStart);
fout << finalDistance + 1;
fin.close();
fout.close();
return 0;
}