Cod sursa(job #1722396)

Utilizator elena.marinicaMarinica Elena-Georgiana elena.marinica Data 27 iunie 2016 23:09:49
Problema Diametrul unui arbore Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

int bfs(int s, int dist[], std::vector<int> g[], int n) {
	
	int node; // ultimul nod descoperit
	std::queue<int> q;
	bool visited[n + 1];
	memset(visited, false, sizeof(bool) * (n + 1));
	
	q.push(s);
	visited[s] = true;
	
	
	while (!q.empty()) {
		
		node = q.front();
		q.pop();
	
		for (unsigned int i = 0; i < g[node].size(); i++) {
			if (!visited[g[node][i]]) {
			
				visited[g[node][i]] = true;
				q.push(g[node][i]);
				dist[g[node][i]] = dist[node] + 1;
			}
		}
	}
	
	return node;
}

int main() {
	
	ifstream fin("darb.in");
	ofstream fout("darb.out");
	
	int N, u, v, d;
	
	fin >> N;
	vector<int> graph[N + 1];
	int dist[N + 1];
	memset(dist, 0, sizeof(int) * (N + 1));
	
	
	for (int i = 1; i < N; i++) {
		fin >> u >> v;
		
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	

	d = 0;
	int last = bfs(1, dist, graph, N);
	d += dist[last];
	
	int l = bfs(last, dist, graph, N);

	fout << (d + dist[last]);
	
	
	fin.close();
	fout.close();
	
	return 0;
	
}