Cod sursa(job #2211123)

Utilizator zvonTutuldunsa Voronokda zvon Data 9 iunie 2018 13:51:36
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#include<queue>
#include"string.h"
using namespace std;

ifstream fi("darb.in");
ofstream fo("darb.out");
vector < vector <int> > v;
char viz[100005];
int depth[100005];
int n;

int farthest(int source, int &maxdepth) {
	queue <int> q;
	int last;
	q.push(source);
	memset(viz, 0, n + 1);
	memset(depth, 0, sizeof(int) * (n + 1));
	while(!q.empty()) {
		int node = q.front();
		for (int i = 0; i < v[node].size(); i++) {
			int son = v[node][i];
			if (!viz[son]) {
				q.push(son);
				viz[son] = 1;
				depth[son] = depth[node] + 1;
			}
			maxdepth = depth[node];
			last = node;
		}
		q.pop();
	}
	return last;
}

int main() {
	int a, b, i;
	fi >> n;
	v.resize(n + 1);
	for (i = 0; i < n; i++) {
		fi >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	int maxdepth;
	int last;
	last = farthest (1, maxdepth);
	last = farthest (last, maxdepth);
	fo << maxdepth + 1;
	
	fi.close();
	fo.close();
	return 0; 
}