Cod sursa(job #2660954)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 20 octombrie 2020 22:12:19
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> arcs;
vector<int> used;

int n;

int bfs(int startnode) {
	queue<int> q;
	used.assign(n+2, 0);

	used[startnode] = 1;
	int last = startnode, current_node, next_node;

	q.push(startnode);
	while(q.size()) {
		current_node = q.front();
		q.pop();
		for(int i=0; i<arcs[current_node].size(); ++i) {
			next_node = arcs[current_node][i];
			if (used[next_node] == 0) {
				used[next_node] = used[current_node] + 1;
				last = next_node;
				q.push(next_node);
			}
		}
	}

	return last;
}


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

	int x, y;
	scanf("%d", &n);
	arcs.resize(n+2);

	for(int i=0; i<n; ++i) {
		scanf("%d%d", &x, &y);
		arcs[x].push_back(y);
		arcs[y].push_back(x);
	}

	printf("%d\n", used[bfs(bfs(1))]);
	return 0;
}