Cod sursa(job #2196665)

Utilizator firutibogdanFiruti Bogdan-Cristian firutibogdan Data 20 aprilie 2018 00:02:50
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int kNmax = 100005;

class Task {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	int n;
	vector<int> adj[kNmax];

	void read_input() {
		ifstream fin("darb.in");
		int x, y;
		fin >> n;
		while (fin >> x >> y) {
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
		fin.close();
	}

	int get_result() {
		int dmax = -1;
		int second_source = -1;
		vector<int> d(n + 1, -1);
		queue<int> q;

		q.push(1);
		d[1] = 0;
		dmax = 0;

		while (!q.empty()) {
			int node = q.front();
			q.pop();
			for (int neighbour : adj[node]) {
				if (d[neighbour] == -1) {
					d[neighbour] = d[node] + 1;
					if (d[neighbour] > dmax) {
						dmax = d[neighbour];
						second_source = neighbour;
					}
					q.push(neighbour);
				}
			}
		}

		for (int i = 1; i < n; ++i) {
			d[i] = -1;
		}

		q.push(second_source);
		d[second_source] = 0;
		dmax = 0;

		while (!q.empty()) {
			int node = q.front();
			q.pop();
			for (int neighbour : adj[node]) {
				if (d[neighbour] == -1) {
					d[neighbour] = d[node] + 1;
					if (d[neighbour] > dmax) {
						dmax = d[neighbour];
					}
					q.push(neighbour);
				}
			}
		}

		return dmax + 1;
	}

	void print_output(int result) {
		ofstream fout("darb.out");
		fout << result << "\n";
		fout.close();
	}
};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}