Cod sursa(job #1379091)

Utilizator BonCipBonciocat Ciprian Mircea BonCip Data 6 martie 2015 16:14:38
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <utility>
#define NMAX 100000
using namespace std;

vector<int> E[NMAX + 1];
bool bfs[NMAX + 1];

int BFS1()
{
	queue<int> q;
	q.push(1);
	bfs[1] = 1;
	int term;
	while (!q.empty()) {
		term = q.front();
		q.pop();
		for (int i = 0; i < E[term].size(); ++i) {
			if (!bfs[E[term][i]]) {
				bfs[E[term][i]] = 1;
				q.push(E[term][i]);
			}
		}
	}
	return term;
}

int BFS2()
{
	queue< pair<int,int> > q;
	int aux = BFS1();
	memset((char*)bfs, 0, sizeof(bfs));
	q.push(make_pair(aux, 1));
	bfs[aux] = 1;
	pair<int,int> term;
	while (!q.empty()) {
		term = q.front();
		q.pop();
		for (int i = 0; i < E[get<0>(term)].size(); ++i) {
			if (!bfs[E[get<0>(term)][i]]) {
				bfs[E[get<0>(term)][i]] = 1;
				q.push(make_pair(E[get<0>(term)][i], get<1>(term) + 1));
			}
		}
	}
	return get<1>(term);
}

int main()
{
	FILE *fin, *fout;
	fin = fopen("darb.in", "r");
	fout = fopen("darb.out", "w");

	int N;
	fscanf(fin, "%d", &N);

	int i;
	for (i = 1; i < N; ++i) {
		int x, y;
		fscanf(fin, "%d%d", &x, &y);
		E[x].push_back(y);
		E[y].push_back(x);
	}

	fprintf(fout, "%d\n", BFS2());

	fclose(fin);
	fclose(fout);
	return 0;
}