Cod sursa(job #1611131)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 23 februarie 2016 22:42:42
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#define MOD 1000000007
#define NMAX 100005
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

FILE *fin = freopen("darb.in", "r", stdin);
FILE *fout = freopen("darb.out", "w", stdout);

typedef pair<int, int> pii;

vector<int> v[NMAX];
int dist[NMAX];

int BFS(int start);

int main() {
	int n, i, x, y, a, b;

	scanf("%d", &n);
	for (i = 1; i < n; ++i) {
		scanf("%d%d", &x, &y);

		v[x].pb(y);
		v[y].pb(x);
	}

	a = BFS(1);
	b = BFS(a);

	cout << dist[b];

	return 0;
}

int BFS(int start) {
	int x, i, y;

	memset(dist, 0, sizeof(dist));
	queue<int> Q;
	Q.push(start);
	dist[start] = 1;

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

		for (i = 0; i < v[x].size(); ++i) {
			y = v[x][i];

			if (!dist[y]) {
				dist[y] = dist[x] + 1;
				Q.push(y);
			}
		}
	}

	return x;
}