Cod sursa(job #2423572)

Utilizator Marius2902Chitac Marius Marius2902 Data 21 mai 2019 18:24:07
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#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(1, max_dist_node);
	out << G.BFS(max_dist_node, max_dist_node);
	return 0;
}