Cod sursa(job #2533584)

Utilizator radustn92Radu Stancu radustn92 Data 29 ianuarie 2020 13:06:25
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int NMAX = 100505;

int N;
bool visited[NMAX];
vector<int> G[NMAX];

void read() {
	scanf("%d", &N);
	int x, y;
	for (int edgeIdx = 0; edgeIdx < N - 1; edgeIdx++) {
		scanf("%d%d", &x, &y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
}

void bfs(int start, int& furthestNode, int& dist) {
	queue<int> queue;
	vector<bool> visited(N + 1, false);
	vector<int> D(N + 1, N);

	queue.push(start);
	D[start] = 0;
	while (!queue.empty()) {
		int node = queue.front();
		queue.pop();

		for (auto& neighbour : G[node]) {
			if (!visited[neighbour]) {
				visited[neighbour] = true;
				D[neighbour] = D[node] + 1;
				queue.push(neighbour);
			}
		}

		furthestNode = node;
		dist = D[node];
	}
}

int main() {
	freopen("darb.in", "r", stdin);
	freopen("darb.out", "w", stdout);

	read();

	int furthestNode, furthestDist;
	bfs(1, furthestNode, furthestDist);
	bfs(furthestNode, furthestNode, furthestDist);
	printf("%d\n", furthestDist + 1);
	return 0;
}