Cod sursa(job #2207260)

Utilizator cyborgGavrila Alex cyborg Data 25 mai 2018 13:21:05
Problema Diametrul unui arbore Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <list>
#include <queue>
#include <algorithm>
using namespace std;

int bfs(vector<pair<int, int> > arbore, int &diam,int nod) {
	vector<int> viz(arbore.size() + 1, 0);
	vector<int> prev(arbore.size() + 1, -1);
	queue<int> q;
	//for (pair<int, int> adc : arbore) cout << adc.first << " " << adc.second << endl;
	viz[nod] = 1;
	q.push(nod);
	//cout << q.front();
	while (!q.empty()) {
		int i = q.front();
		//cout << i<<" ";
		q.pop();
		for (pair<int, int> a : arbore) {
			//cout << (a.first == i && !viz[a.second]);
			if (a.first == i && !viz[a.second]) {
				//cout << "aaa";
				prev[a.second] = i;
				viz[a.second] = viz[prev[a.second]] + 1;
				q.push(a.second);
			}else if (a.second == i && !viz[a.first]) {
				//cout << "aaa";
				prev[a.first] = i;
				viz[a.first] = viz[prev[a.first]] + 1;
				q.push(a.first);
			}
		}
	}
	//for (int a : viz) cout << a;
	diam = *max_element(std::begin(viz), std::end(viz));
	for (int b = 0; b < viz.size(); b++) {
		if (viz[b] == diam) return b;
	}
 
}



int diam(vector<pair<int, int> > arbore) {
	int nod1,nod2;
	int di = 0;
	nod1=bfs(arbore, di,0);
	nod2 = bfs(arbore, di, nod1);
	return di;

}

int main() {
	int n,a,b;
	ifstream f("darb.in");
	ofstream f1("darb.out");
	vector < pair<int, int> > arbore;
	f >> n;
	while (f >> a >> b) {
		arbore.push_back(make_pair(a-1, b-1));
	}

	f1<<diam(arbore);
	f.close();
	f1.close();
	return 0;
}