Pagini recente » Cod sursa (job #2175176) | Cod sursa (job #1418155) | Cod sursa (job #1480867) | Istoria paginii runda/concurs_000004/clasament | Cod sursa (job #2423613)
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
using namespace std;
class Tree {
int n;
list<int> *adj;
public:
Tree(int);
~Tree() { delete[] adj; }
void addEdge(int, int);
int BFS(int,int&);
};
Tree::Tree(int n)
{
this->n = n;
adj = new list<int>[n+1];
}
void Tree::addEdge(int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
int Tree::BFS(int st,int& max_dist_node)
{
bool *visited = new bool[n + 1];
int *l = new int[n + 1];
int i,aux;
for (i = 1; i <= n; i++)
l[i] = visited[i] = 0;
l[st] = 1;
max_dist_node = 0;
queue<int> Q;
Q.push(st);
while (!Q.empty())
{
aux = Q.front();
visited[aux] = true;
Q.pop();
list<int>::iterator it;
for (it = adj[aux].begin(); it != adj[aux].end(); it++)
if (!visited[*it])
{
max_dist_node = *it;
l[*it] = l[aux] + 1;
Q.push(*it);
}
}
delete[] visited;
int lung=l[max_dist_node];
delete[] l;
return lung;
}
int main()
{
ifstream in("darb.in");
ofstream out("darb.out");
int n, i, u, v;
in >> n;
Tree G(n);
for (i = 0; i < n - 1; i++)
{
in >> u >> v;
G.addEdge(u, v);
}
int max_dist_node=0;
G.BFS(n/2, max_dist_node);
out << G.BFS(max_dist_node, max_dist_node);
return 0;
}