Cod sursa(job #1462248)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 17 iulie 2015 15:12:40
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <queue>
#include <vector>

#define NMax 100010

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

int nodes, dist[NMax], leaf, Max = -1;
bool mark[NMax];
queue<int> Q;
vector<int> G[NMax];

void BFS(int node)
{
	Q.push(node);

	for (int i = 1; i <= nodes; i++) {
		dist[i] = 0;
		mark[i] = false;
	}

	mark[node] = true;

	while (!Q.empty()) {
		
		int crtNode = Q.front();
		Q.pop();

		for (vector<int>::iterator it = G[crtNode].begin(); it != G[crtNode].end(); it++) {
			if (!mark[*it]) {
				Q.push(*it);
				mark[*it] = true;

				dist[*it] = dist[crtNode] + 1;

				Max = dist[*it];
				leaf = *it;
			}
		}

	}
}

int main()
{
	f >> nodes;

	int n1, n2;
	for (int i = 1; i <= nodes; i++) {
		f >> n1 >> n2;

		G[n1].push_back(n2);
		G[n2].push_back(n1);
	}

	BFS(1);
	BFS(leaf);

	g << Max + 1;

	return 0;
}