Cod sursa(job #1188009)

Utilizator sorin2kSorin Nutu sorin2k Data 18 mai 2014 20:07:14
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<fstream>
#include<queue>
#include<vector>
#include<bitset>
using namespace std;

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

int n, dist[100000];
bitset<100000> viz;
vector<int> arb[100000];

// returneaza ultimul nod din parcurgere (cel cu distanta cea mai mare)
int bfs(int start) {
	int current;
	queue<int> q;
	q.push(start);
	viz[start] = 1;
	dist[start] = 0;
	while(!q.empty()) {
		current = q.front();
		q.pop();
		for(vector<int>::iterator it = arb[current].begin(); it != arb[current].end(); ++it) {
			if(viz[*it] == 0) {
				viz[*it] = 1;
				q.push(*it);
				dist[*it] = 1 + dist[current];
			}
		}
	}
	return current;
}

int main() {
	int i, u, v;
	fin >> n;
	for(i = 0; i < n-1; i++) {
		fin >> u >> v;
		arb[u-1].push_back(v-1);
		arb[v-1].push_back(u-1);
	}
	u = bfs(0);
	viz.reset();
	v = bfs(u);
	fout << dist[v] + 1 << "\n";
	return 0;
}