Cod sursa(job #2189006)

Utilizator claudiu.gatinaFMI Claudiu Gatina claudiu.gatina Data 27 martie 2018 16:58:51
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

class Graf
{
	int n, m;
	vector<int> adjList[100001];
	
public:
	Graf()
	{
		n = 0;
		m = 0;
	}
	
	void setN(int N)
	{
		n = N;
	}
	
	void add(int a, int b)
	{
		++n;
		adjList[a].push_back(b);
		adjList[b].push_back(a);
	}
	
	int mDistantaCeaMaiMare(int &start)
	{
		vector<int> v(n, 0);
		vector<int> d(n, 0);
		v[start] = 1;
		int distantaCeaMaiMare = 0;
		int celMaiIndepartatNod = 0;
		queue<int> BFS;
		BFS.push(start);
		while(!BFS.empty())
		{
			int nodCurent = BFS.front();
			for(int i = 0; i < adjList[nodCurent].size(); ++i)
			{
				int nodUrmator = adjList[nodCurent][i];
				if(!v[nodUrmator]) {
					v[nodUrmator] = 1;
					BFS.push(nodUrmator);
					d[nodUrmator] = d[nodCurent] + 1;
					if(d[nodUrmator] > distantaCeaMaiMare) {
						distantaCeaMaiMare = d[nodUrmator];
						celMaiIndepartatNod = nodUrmator;
					}
				}
				BFS.pop();
			}
		}
		start = celMaiIndepartatNod;
		return distantaCeaMaiMare;
	}
	
	int diametru()
	{
		int start = 0;
		mDistantaCeaMaiMare(start);
		return mDistantaCeaMaiMare(start);
	}
			
};

int main()
{
	int N;
	Graf arb;
	freopen("darb.in", "r", stdin);
	freopen("darb.out", "w", stdout);
	
	cin >> N;
	for(int i = 0; i < N - 1; ++i)
	{
		int a, b;
		cin >> a >> b;
		arb.add(--a, --b);
	}
	cout << arb.diametru();
	return 0;
}