Cod sursa(job #2794684)

Utilizator schizofrenieShallan Davar schizofrenie Data 5 noiembrie 2021 11:54:41
Problema Diametrul unui arbore Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>

#define MAXN 100000

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

bool dfs_viz[MAXN];
bool bfs_viz[MAXN];
int ret;

void
dfs (int de) {
	++ ret;
	dfs_viz[de] = true;
	for (auto la: muchii[de])
		if (!dfs_viz[la])
			dfs(la);
	printf("%d\n",  ret);
	exit(0);
}

int
bfs (int start) {
	std::queue<int> q;
	int now;

	q.emplace(start);

	bfs_viz[start] = true;

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

		for (auto la: muchii[now])
			if (!bfs_viz[la]) {
				q.emplace(la);
				bfs_viz[la] = 1;
			}
	}

	return now;
}

int
main () {
	int n;
	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);
	}

	dfs(bfs(0));

	return 0;
}