Cod sursa(job #2693445)

Utilizator davidcotigacotiga david davidcotiga Data 5 ianuarie 2021 22:43:37
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <set>
#include <algorithm>
#include <stack>
#include <vector>
#include <iomanip>
#include <cstdio>

using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

#define MAX 100005

int n;
bool visited[MAX];
int Distance[MAX];
vector<int> A[MAX];
queue<int> Q;

int BFS() {
	int Node, Next;
	int rez;


	while (!Q.empty()) {
		rez = Q.front();
		Node = Q.front();
		visited[Node] = 1;
		Q.pop();

		for (unsigned int i = 0; i < A[Node].size(); ++i) {
			Next = A[Node][i];

			if (!visited[Next]) {
				Q.push(Next);
				visited[Next] = 1;
			}
		}
	}
	return rez;
}

int BFS2() {
	int Node, Next;
	int maxim = 0;

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

		for (unsigned int i = 0; i < A[Node].size(); ++i) {
			Next = A[Node][i];

			if (Distance[Next] == -1) {
				Q.push(Next);
				Distance[Next] = Distance[Node] + 1;
				maxim = max(maxim, Distance[Next]);
			}
		}
	}
	return maxim;
}


int main() {
	fin >> n;

	int a, b;
	for (int i = 1; i < n; ++i) {
		fin >> a >> b;
		A[a].push_back(b);
		A[b].push_back(a);
	}

	Q.push(b);

	int node = BFS();

	Q.push(node);

	for (int i = 1; i <= n; ++i)
		Distance[i] = -1;
	Distance[node] = 0;

	fout << BFS2() + 1;

	return 0;
}