Cod sursa(job #2794700)

Utilizator schizofrenieShallan Davar schizofrenie Data 5 noiembrie 2021 12:12:28
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>

#define MAXN 100000

std::vector<int> muchii[MAXN];

int mem1[MAXN];
int mem2[MAXN];

int *depth;
int n;

template <bool second_pass = false>
int
bfs (int start) {
	int now;
	std::queue<int> q;

	if constexpr (second_pass)
		depth = mem2;
	else
		depth = mem1;

	q.emplace(start);

	depth[start] = 1;

	while (!q.empty()) {
		now = q.front();
		q.pop();

		for (auto la: muchii[now])
			if (depth[la] == 0) {
				q.emplace(la);
				depth[la] = (second_pass ? depth[now] : 0) + 1;
			}
	}

	if constexpr (second_pass)
		return depth[now];
	else
		return now;
}

int
main () {
	int i;
	int start;

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

	scanf("%d", &n);

	for (i = 0; i != n - 1; ++ i) {
		int de, la;

		scanf("%d%d", &de, &la);
		-- de, -- la;

		start = de;

		muchii[de].emplace_back(la);
		muchii[la].emplace_back(de);
	}

	start = bfs(0);

	printf("%d\n", bfs<true>(start));

	return 0;
}