Cod sursa(job #1774220)

Utilizator RobertSSamoilescu Robert RobertS Data 8 octombrie 2016 18:17:09
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

int N;
const int MAX_N = 100001;
vector<int> graph[MAX_N];



int BFS(int nod, int &deepest) {

	queue<int> q;
	q.push(nod);

	

	int cost[MAX_N];
	bool vis[MAX_N];

	memset(cost, 0, sizeof(cost));
	memset(vis, false, sizeof(vis));

	vis[nod] = true;
	cost[nod] = 1;

	while (!q.empty()) {
		deepest = q.front();
		q.pop();

		for (size_t i = 0; i < graph[deepest].size(); i++) {
			int next_node = graph[deepest][i];
			
			if (!vis[next_node]) {
				vis[next_node] = true;
				q.push(next_node);
				cost[next_node] = 1 + cost[deepest];
			}
		}


	}

	return cost[deepest];

}

int main() {

	fin >> N;
	for (int i = 0; i < N - 1; i++) {
		int n1, n2;
		fin >> n1 >> n2;
		graph[n1].push_back(n2);
		graph[n2].push_back(n1);
	}

	int deepest1, deepest2, cost;
	cost = BFS(1, deepest1);
	cost = BFS(deepest1, deepest2);

	fout << cost << '\n';


	fin.close();
	fout.close();

	return 0;
}