Cod sursa(job #1958061)

Utilizator cazonirobertCazoni robert cazonirobert Data 7 aprilie 2017 23:13:56
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <stack>
#include <list>	
#include <algorithm>
#include <limits.h>
#include <queue>
#include <utility>
#include <set>
#include <unordered_set>

using namespace std;

//longest chain in a tree

ifstream f("darb.in");
ofstream g("darb.out");
int n, m;
vector<int> tree[100001];

pair<int, int> BFSdistances (int root);

int longestChain(int root){
	pair<int, int> res1 = BFSdistances(root);
	//cout << res1.first << " " << res1.second << endl;

	pair<int, int> res2 = BFSdistances(res1.first);
	//cout << res2.first << " " << res2.second << endl;

	return res2.second + 1; // we include the start node aswell

}

pair<int, int> BFSdistances (int root){
	int maxDistance = -1;
	int maxDistanceNode;
	queue<pair<int, int> > q;

	unordered_set<int> visited;

	q.push(pair<int, int> (root,0));

	while (!(q.empty())){
		pair<int, int> inter = q.front();
		q.pop();
		visited.insert(inter.first);

		if(inter.second > maxDistance){
			maxDistance = inter.second;
			maxDistanceNode = inter.first;
		}

		//cout << inter.first << " " << inter.second << endl;

		for(int node: tree[inter.first]){
			if(visited.find(node) == visited.end())
				q.push(pair<int, int> (node, inter.second + 1));
		}

	}
	return pair<int, int>(maxDistanceNode, maxDistance);
}

int main(){
	f >> n;
	m = n - 1;
	for(int i = 0; i < m; i++){
		int from, to;
		f >> from >> to;
		tree[from].push_back(to);
		tree[to].push_back(from);
	}

	g << longestChain(1) << endl;

	return 0;

}