Cod sursa(job #2200742)

Utilizator anamaria.visanAnamaria Visan anamaria.visan Data 2 mai 2018 13:18:52
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 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");
		fin >> n;
		for (int i = 1, x, y; i < n; i++) {
			fin >> x >> y;
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
		fin.close();
	}

	int get_result() {
		vector<int> d(n + 1);

		for(int i = 1; i <= n; i++){
			d[i] = -1;
		}
		int source = 1;
		d[source] = 0;
		queue<int> q;
		q.push(source);
		while(!q.empty()){
			int n = q.front();
			source = n;
			q.pop();
			for(int i = 0; i < adj[n].size(); i++){
				if(d[adj[n][i]] == -1){
					q.push(adj[n][i]);
					d[adj[n][i]] = d[n] + 1;
				}
			}
		}
		for(int i = 1; i <= n; i++){
			d[i] = 0;
		}
		return dfs(source, d);
	}

	int dfs(int node, vector<int> &visited){
		visited[node] = 1;
		int result = 1;
		for(int i = 0; i < adj[node].size(); i++){
			if(visited[adj[node][i]] == 0){
				result = max(1 + dfs(adj[node][i], visited), result);
			}
		}
		return result;
	}

	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;
}