Pagini recente » Cod sursa (job #2755867) | Cod sursa (job #799735) | Cod sursa (job #846833) | Cod sursa (job #1597983) | Cod sursa (job #2423541)
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
using namespace std;
class Tree {
int n;
list<int> *adj;
public:
Tree(int);
~Tree() {}
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 i,aux,lungime=0,ok=0;
for (i = 1; i <= n; i++)
visited[i] = false;
max_dist_node = 0;
queue<int> Q;
Q.push(st);
while (!Q.empty())
{
ok = 0;
aux = Q.front();
visited[aux] = true;
max_dist_node = aux;
Q.pop();
list<int>::iterator it;
for (it = adj[aux].begin(); it != adj[aux].end(); it++)
if (!visited[*it])
{
ok = 1;
Q.push(*it);
}
if (ok)
lungime++;
}
return lungime;
}
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;
G.BFS(1, max_dist_node);
out << G.BFS(max_dist_node, max_dist_node);
return 0;
}